Cost Based Tower of Hanoi | Python3 implementation of the approach ; Function to initialize the dp table ; Initialize with maximum value ; Function to return the minimum cost ; Base case ; If problem is already solved , return the pre - calculated answer ; Number of the auxiliary disk ; Initialize the minimum cost as Infinity ; Calculationg the cost for first case ; Calculating the cost for second case ; Minimum of both the above cases ; Store it in the dp table ; Return the minimum cost ; Driver code
import numpy as np NEW_LINE import sys NEW_LINE RODS = 3 NEW_LINE N = 3 NEW_LINE dp = np . zeros ( ( N + 1 , RODS + 1 , RODS + 1 ) ) ; NEW_LINE def initialize ( ) : NEW_LINE INDENT for i in range ( N + 1 ) : NEW_LINE INDENT for j in range ( 1 , RODS + 1 ) : NEW_LINE INDENT for k in range ( 1 , RODS + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] [ k ] = sys . maxsize ; NEW_LINE DEDENT DEDENT DEDENT DEDENT def mincost ( idx , src , dest , costs ) : NEW_LINE INDENT if ( idx > N ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ idx ] [ src ] [ dest ] != sys . maxsize ) : NEW_LINE INDENT return dp [ idx ] [ src ] [ dest ] ; NEW_LINE DEDENT rem = 6 - ( src + dest ) ; NEW_LINE ans = sys . maxsize ; NEW_LINE case1 = costs [ src - 1 ] [ dest - 1 ] + mincost ( idx + 1 , src , rem , costs ) + mincost ( idx + 1 , rem , dest , costs ) ; NEW_LINE case2 = ( costs [ src - 1 ] [ rem - 1 ] + mincost ( idx + 1 , src , dest , costs ) + mincost ( idx + 1 , dest , src , costs ) + costs [ rem - 1 ] [ dest - 1 ] + mincost ( idx + 1 , src , dest , costs ) ) ; NEW_LINE ans = min ( case1 , case2 ) ; NEW_LINE dp [ idx ] [ src ] [ dest ] = ans ; NEW_LINE return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT costs = [ [ 0 , 1 , 2 ] , [ 2 , 0 , 1 ] , [ 3 , 2 , 0 ] ] ; NEW_LINE initialize ( ) ; NEW_LINE print ( mincost ( 1 , 1 , 3 , costs ) ) ; NEW_LINE DEDENT