The standard Tower of Hanoi problem is explained here . In the standard problem, all the disc transactions are considered identical. Given a 3×3 matrix costs[][] containing the costs of transfer of disc between the rods where costs[i][j] stores the cost of transferring a disc from rod i to rod j. Cost of transfer between the same rod is 0. Hence the diagonal elements of the cost matrix are all 0s. The task is to print the minimum cost in which all the N discs are transferred from rod 1 to rod 3.
Examples:
Input: N = 2
costs = {
{ 0, 1, 2},
{ 2, 0, 1},
{ 3, 2, 0}}
Output: 4
There are 2 discs, the smaller one is on the bigger one.
Transfer the smaller disc from rod 1 to rod 2.
Cost of this transfer is equal to 1
Transfer the bigger disc from rod 1 to rod 3.
Cost of this transfer is equal to 2.
Transfer the smaller disc from rod 2 to rod 3.
Cost of this transfer is equal to 1
Total minimum cost is equal to 4.
Input: N = 3
costs = {
{ 0, 1, 2},
{ 2, 0, 1},
{ 3, 2, 0}}
Output: 12
Approach: Idea is to use Top-down Dynamic programming.
Let’s say mincost(idx, src, dest) be the minimum cost for transferring the discs of indices idx to N from rod src to rod dest. The third rod which is neither the source nor the destination rod would have the value rem = 6 – (i + j) as the rod numbers are 1, 2 and 3 and their sum is 6. If 1st and 3rd rods are the source and destination respectively then the auxiliary rod will have number as 6 – (1 + 3) = 2.
Now break the problem into its subproblems as follows:
- Case 1: First transfer all the discs with index (idx + 1) to N to the remaining rod. Now transfer the largest disc to destination rod. Again transfer all the discs from remaining rod to the destination rod. This process would cost as.
Cost = mincost(idx + 1, src, rem) + costs[src][dest] + mincost(idx + 1, rem, dest)
- Case 2: First transfer all the discs with index (idx + 1) to N to the destination rod. Now transfer the largest disc to remaining rod. Again transfer all the discs from destination rod to the source rod. Now transfer the largest disc from remaining rod to the destination rod. Again transfer the discs from source rod to destination rod. This process would cost as:
Cost = mincost(idx + 1, src, dest) + costs[src][rem] + mincost(idx + 1, dest, src) + cost[rem][dest] + mincost(idx + 1, src, dest)
- Answer would be equal to the minimum of the above two cases.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define RODS 3#define N 3int dp[N + 1][RODS + 1][RODS + 1];// Function to initialize the dp tablevoid initialize(){ // Initialize with maximum value for (int i = 0; i <= N; i += 1) { for (int j = 1; j <= RODS; j++) { for (int k = 1; k <= RODS; k += 1) { dp[i][j][k] = INT_MAX; } } }}// Function to return the minimum costint mincost(int idx, int src, int dest, int costs[RODS][RODS]){ // Base case if (idx > N) return 0; // If problem is already solved, // return the pre-calculated answer if (dp[idx][src][dest] != INT_MAX) return dp[idx][src][dest]; // Number of the auxiliary disk int rem = 6 - (src + dest); // Initialize the minimum cost as Infinity int ans = INT_MAX; // Calculating the cost for first case int case1 = costs[src - 1][dest - 1] + mincost(idx + 1, src, rem, costs) + mincost(idx + 1, rem, dest, costs); // Calculating the cost for second case int 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); // Minimum of both the above cases ans = min(case1, case2); // Store it in the dp table dp[idx][src][dest] = ans; // Return the minimum cost return ans;}// Driver codeint main(){ int costs[RODS][RODS] = { { 0, 1, 2 }, { 2, 0, 1 }, { 3, 2, 0 } }; initialize(); cout << mincost(1, 1, 3, costs); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG{ static int RODS = 3;static int N = 3;static int [][][]dp=new int[N + 1][RODS + 1][RODS + 1];// Function to initialize the dp tablestatic void initialize(){ // Initialize with maximum value for (int i = 0; i <= N; i += 1) { for (int j = 1; j <= RODS; j++) { for (int k = 1; k <= RODS; k += 1) { dp[i][j][k] = Integer.MAX_VALUE; } } }}// Function to return the minimum coststatic int mincost(int idx, int src, int dest,int costs[][]){ // Base case if (idx > N) return 0; // If problem is already solved, // return the pre-calculated answer if (dp[idx][src][dest] != Integer.MAX_VALUE) return dp[idx][src][dest]; // Number of the auxiliary disk int rem = 6 - (src + dest); // Initialize the minimum cost as Infinity int ans = Integer.MAX_VALUE; // Calculating the cost for first case int case1 = costs[src - 1][dest - 1] + mincost(idx + 1, src, rem, costs) + mincost(idx + 1, rem, dest, costs); // Calculating the cost for second case int 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); // Minimum of both the above cases ans = Math.min(case1, case2); // Store it in the dp table dp[idx][src][dest] = ans; // Return the minimum cost return ans;}// Driver codepublic static void main (String[] args) { int [][]costs = { { 0, 1, 2 }, { 2, 0, 1 }, { 3, 2, 0 } }; initialize(); System.out.print (mincost(1, 1, 3, costs)); }}// This code is contributed by ajit..23@ |
Python3
# Python3 implementation of the approach import numpy as npimport sysRODS = 3N = 3dp = np.zeros((N + 1,RODS + 1,RODS + 1)); # Function to initialize the dp table def initialize() : # Initialize with maximum value for i in range(N + 1) : for j in range(1, RODS + 1) : for k in range(1, RODS + 1) : dp[i][j][k] = sys.maxsize; # Function to return the minimum cost def mincost(idx, src, dest, costs) : # Base case if (idx > N) : return 0; # If problem is already solved, # return the pre-calculated answer if (dp[idx][src][dest] != sys.maxsize) : return dp[idx][src][dest]; # Number of the auxiliary disk rem = 6 - (src + dest); # Initialize the minimum cost as Infinity ans = sys.maxsize; # Calculating the cost for first case case1 = costs[src - 1][dest - 1] + mincost(idx + 1, src, rem, costs) + mincost(idx + 1, rem, dest, costs); # Calculating the cost for second case 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)); # Minimum of both the above cases ans = min(case1, case2); # Store it in the dp table dp[idx][src][dest] = ans; # Return the minimum cost return ans; # Driver code if __name__ == "__main__" : costs = [ [ 0, 1, 2 ], [ 2, 0, 1 ], [ 3, 2, 0 ] ]; initialize(); print(mincost(1, 1, 3, costs)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{ static int RODS = 3;static int N = 3;static int [,,]dp=new int[N + 1,RODS + 1,RODS + 1];// Function to initialize the dp tablestatic void initialize(){ // Initialize with maximum value for (int i = 0; i <= N; i += 1) { for (int j = 1; j <= RODS; j++) { for (int k = 1; k <= RODS; k += 1) { dp[i,j,k] = int.MaxValue; } } }}// Function to return the minimum coststatic int mincost(int idx, int src, int dest,int [,]costs){ // Base case if (idx > N) return 0; // If problem is already solved, // return the pre-calculated answer if (dp[idx,src,dest] != int.MaxValue) return dp[idx,src,dest]; // Number of the auxiliary disk int rem = 6 - (src + dest); // Initialize the minimum cost as Infinity int ans = int.MaxValue; // Calculating the cost for first case int case1 = costs[src - 1,dest - 1] + mincost(idx + 1, src, rem, costs) + mincost(idx + 1, rem, dest, costs); // Calculating the cost for second case int 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); // Minimum of both the above cases ans = Math.Min(case1, case2); // Store it in the dp table dp[idx,src,dest] = ans; // Return the minimum cost return ans;}// Driver codepublic static void Main (String[] args) { int [,]costs = { { 0, 1, 2 }, { 2, 0, 1 }, { 3, 2, 0 } }; initialize(); Console.WriteLine(mincost(1, 1, 3, costs)); }}/* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation of the approach let RODS = 3; let N = 3; let dp = new Array(N + 1); // Function to initialize the dp table function initialize() { // Initialize with maximum value for (let i = 0; i <= N; i += 1) { dp[i] = new Array(RODS + 1); for (let j = 1; j <= RODS; j++) { dp[i][j] = new Array(RODS + 1); for (let k = 1; k <= RODS; k += 1) { dp[i][j][k] = Number.MAX_VALUE; } } } } // Function to return the minimum cost function mincost(idx, src, dest, costs) { // Base case if (idx > N) return 0; // If problem is already solved, // return the pre-calculated answer if (dp[idx][src][dest] != Number.MAX_VALUE) return dp[idx][src][dest]; // Number of the auxiliary disk let rem = 6 - (src + dest); // Initialize the minimum cost as Infinity let ans = Number.MAX_VALUE; // Calculating the cost for first case let case1 = costs[src - 1][dest - 1] + mincost(idx + 1, src, rem, costs) + mincost(idx + 1, rem, dest, costs); // Calculating the cost for second case let 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); // Minimum of both the above cases ans = Math.min(case1, case2); // Store it in the dp table dp[idx][src][dest] = ans; // Return the minimum cost return ans; } let costs = [ [ 0, 1, 2 ], [ 2, 0, 1 ], [ 3, 2, 0 ] ]; initialize(); document.write(mincost(1, 1, 3, costs));// This code is contributed by divyeshrabadiya07.</script> |
Output:
12
Time Complexity: O(N) where N is the number of discs in given rod.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
