Java commented DP solution


  • 32
    M

    Big Idea: Given any n, we make a guess k. Then we break the interval [1,n] into [1,k - 1] and [k + 1,n]. The min of worst case cost can be calculated recursively as

    cost[1,n] = k + max{cost[1,k - 1] + cost[k+1,n]}
    Also, it takes a while for me to wrap my head around "min of max cost". My understand is that: you strategy is the best, but your luck is the worst. You only guess right when there is no possibilities to guess wrong.

    public class Solution {
        public int getMoneyAmount(int n) {
            // all intervals are inclusive
            // uninitialized cells are assured to be zero
            // the zero column and row will be uninitialized
            // the illegal cells will also be uninitialized
            // add 1 to the length just to make the index the same as numbers used
            int[][] dp = new int[n + 1][n + 1]; // dp[i][j] means the min cost in the worst case for numbers (i...j)
    
            // iterate the lengths of the intervals since the calculations of longer intervals rely on shorter ones
            for (int l = 2; l <= n; l++) {
                // iterate all the intervals with length l, the start of which is i. Hence the interval will be [i, i + (l - 1)]
                for (int i = 1; i <= n - (l - 1); i++) {
                    dp[i][i + (l - 1)] = Integer.MAX_VALUE;
                    // iterate all the first guesses g
                    for (int g = i; g <= i + (l - 1); g++) {
                        int costForThisGuess;
                        // since if g is the last integer, g + 1 does not exist, we have to separate this case
                        // cost for [i, i + (l - 1)]: g (first guess) + max{the cost of left part [i, g - 1], the cost of right part [g + 1, i + (l - 1)]}
                        if (g == n) {
                            costForThisGuess = dp[i][g - 1] + g;
                        } else {
                            costForThisGuess = g + Math.max(dp[i][g - 1], dp[g + 1][i + (l - 1)]);
                        }
                        dp[i][i + (l - 1)] = Math.min(dp[i][i + (l - 1)], costForThisGuess); // keep track of the min cost among all first guesses
                    }
                }
            }
            return dp[1][n];
        }
    }
    

    Any questions, suggestions & criticism welcomed!


  • 9
    J

    @myanonymos

    a little improvement :)

    public int getMoneyAmount(int n) {
        int[][] dp = new int[n+1][n+1];
        for(int len=1;len<n;len++){
            for(int i=1;i+len<=n;i++){
                int j=i+len;
                int min = Integer.MAX_VALUE;
                for(int k=i;k<j;k++){
                  int tmp = k+Math.max(dp[i][k-1],dp[k+1][j]);
                  min = Math.min(min,tmp);
                }
                dp[i][j] = min;
            }
        }
        return dp[1][n];
    }

  • 0
    M

    @juanren Awesome! Much Shorter and Neater than mine! You know what, I compared my code and yours and I laughed at myself when I saw I kept using i + (l - 1) instead of assigning it to a variable. How dumb was it! Haha!


  • 1
    M

    said in Java commented DP solution:

    you strategy is the best, but your luck is the worst

    "you strategy is the best, but your luck is the worst" This is the best explanation :)


  • 2
    S

    Hi, @juanren your code is concise and neat, but I think some of it could be a bit misleading;

    1.the minimum valid length should 2, because we all know we don't have to cost a single penny to guarantee a win when i==j; and it cannot be explain by the code, we'd better leave it as a corner case;

    2.in the for loop: "for(int i=1;i+len<=n;i++)", we'd better let it be "for(int i=1;i+length-1<=n;i++)" and "int j=i+len-1".

    3.in the for loop "for(int k=i;k<j;k++)", it should be "for(int k=i;k<=j;k++)", because it's necessary to be able to pick j between i......j;

    so I made some modification:

     public int getMoneyAmount(int n) 
    {        
        int[][] dp=new int[n+2][n+2];   
        for(int length=2;length<=n;length++)
        {
        	for(int i=1;i+length-1<=n;i++)
        	{
        		int j=i+length-1;
        		int min=Integer.MAX_VALUE;
        		for(int k=i;k<=j;k++)
        		{
        			int temp=k+Math.max(dp[i][k-1],dp[k+1][j]);
        			min=Math.min(min, temp);
        		}
        		dp[i][j]=min;
        	}
        }
        return dp[1][n];
    }
    

    though your version runs well, but that code above make more sense to me;

    again your code is brilliant, thanks for sharing.


  • 0
    L

    @mustangigem Can you explain any more? What's our strategy? I think the strategy is explicit: when we got "higher", go to the higher half.


  • 0
    B

    The comments within your code really helps me a lot in understanding this problem! Thank you for such a good post!


  • 0
    S
    This post is deleted!

  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.