CODEWITHSUNDEEP
javaalgorithmdynamic-programming
Eric H.
Eric H.

Reputation: 341

How to trace path in a simple dynamic programming prob?

I am trying to solve a simple DP problem:

Given a positive integer n, you can perform any one of the following 3 steps. 1) Subtract 1 from it.
2) If it is divisible by 2, divide by 2.
3) If it is divisible by 3, divide by 3.
Please find the minimum number of steps that takes n to 1 and print out the steps. If there are multiple solutions to achieve the goal in the same number of steps, please print out all these solutions. (if it is hard, at least print out one of these solutions).

Getting the minimum number of steps is not that hard. Simply apply a bottom up DP solution like this:

public int getMinSteps(int n) {
int[] dp = new int[n+1];

int i;
dp[1] = 0; 

for( i = 2 ; i < = n ; i ++ ) {
dp[i] = 1 + dp[i-1];
if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );
if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );
}
return dp[n];
}

However, I was not able to solve the print path part. In a high level, I think I need to stop the "action" at every level a minimum is determined?

Hope I can get some good suggestion or solution here.

thanks!

Upvotes: 2

Views: 3986

Answers (2)

Dante May Code
Dante May Code

Reputation: 11247

Just get another field to store the optimal step, i.e. -1, /2, or /3, if it is optimal to get the minimum path, possibly just using 1, 2, 3 as indicators.

For example, you are comparing a = 1 + dp[i-1], b = 1 + dp[i/2], c = 1 + dp[i/3]. If a is minimum, then you know you should -1 for the number. Store the step as 1. Later, you just jump to the field for i-1 to find the next step until you reach the start point, i.e. 1.

Update:

If you want to print all the paths, you have to store all the optimal steps, and print all the combinations.

In details, you can use three boolean fields for -1, /2, /3 to store if any optimal path goes through a certain number. After that, you can print all the combinations recursively, like traversing a tree.

int[] dp; // for minimum steps
bool[] gominus1;
bool[] godivideby2;
bool[] godivideby3;
List<Integer> steps;

PrintAllPath(int n) {
    if(n == 1) {
        // print steps
        return;
    }
    steps.push_back(n);
    if(gominus1[n]) {
        PrintAllPath(n - 1);
    }
    if(godivideby2[n]) {
        PrintAllPath(n / 2);
    }
    if(govidivideby3[n]) {
        PrintAllPath(n / 3);
    }
    steps.pop_back();
}

Upvotes: 3

Sazzadur Rahaman
Sazzadur Rahaman

Reputation: 7116

Here is How you can retrieve the path:

    public static int getMinSteps(int n) {
    int[] dp = new int[n + 1];
    String[] path = new String[n+1];
    int i;
    dp[1] = 0;
    path[1] = "end";

    for (i = 2; i <= n; i++) {
        dp[i] = 1 + dp[i - 1];
        if (i % 2 == 0) {

            if(dp[i] < 1 + dp[i/2]){
                path[i] = "sub 1," + path[i-1];
            }
            else {
               path[i] = "div by 2," + path[i/2];
            }

            dp[i] = min(dp[i], 1 + dp[i / 2]);

        }

        if (i % 3 == 0) {

             if(dp[i] < 1 + dp[i/3]){
                path[i] = "sub 1," + path[i-1];
            }
            else {
               path[i] = "div by 3," + path[i/3];
            }

            dp[i] = min(dp[i], 1 + dp[i / 3]);
        }

        if( i % 3 != 0 && i % 2 != 0) {
             path[i] = "sub 1," + path[i-1];
        }

    }
    System.out.println("number of steps = "+dp[n]+",path = "+path[n]);
    return dp[n];
}

This is to print single path. To print all the path you need to track all the minimum possible ways to dp[i]. So you need a two dimensional array of String to store them.

Upvotes: 1

Related Questions