Java DP solution


  • 51
    D

    Definition of dp[i][j]: minimum number of money to guarantee win for subproblem [i, j].

    Target: dp[1][n]

    Corner case: dp[i][i] = 0 (because the only element must be correct)

    Equation: we can choose k (i<=k<=j) as our guess, and pay price k. After our guess, the problem is divided into two subproblems. Notice we do not need to pay the money for both subproblems. We only need to pay the worst case (because the system will tell us which side we should go) to guarantee win. So dp[i][j] = min (i<=k<=j) { k + max(dp[i][k-1], dp[k+1][j]) }

    public class Solution {
        public int getMoneyAmount(int n) {
            if (n == 1) {
                return 0;
            }
            int[][] dp = new int[n + 1][n + 1];
            for (int jminusi = 1; jminusi < n; jminusi++) {
                for (int i = 0; i + jminusi <= n; i++) {
                    int j = i + jminusi;
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k <= j; k++) {
                        dp[i][j] = Math.min(dp[i][j],
                                            k + Math.max(k - 1 >= i ? dp[i][k - 1] : 0,
                                                         j >= k + 1 ? dp[k + 1][j] : 0));
                    }
                }
            }
            return dp[1][n];
        }
    }
    

  • 0
    L
    This post is deleted!

  • 8
    F

    Thanks for your idea, I rewrite the code using your idea:

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

  • 23

    @fhqplzj Elegant bottom-up approach! I made some change on variable name to make it more readable. Thanks for your sharing!

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

  • 0
    Y

    @cdai Nice! Could you explain why should we create an array dp of n+2 length? I tried n+1 and met compile error, but I don't know why n+2 works.


  • 1

    @ysx0605hotmail.com Please note that in the innermost loop we reach dp[from][k-1] and dp[to][k+1] where dp[0] and dp[n+1] are required. So we create array of n+2 length;


  • 0
    Y

    @cdai Uh I missed k+1, thank you!


  • 0

  • 0
    S

    What's the complexity of this method?


  • 0
    D

    @shenrf22 It looks like the complexity is O(n^3) because there are n^2 subproblems, and each subproblem takes O(n) time to compute.


  • 0
    This post is deleted!

  • 0
    M

    @dachuan.huang thx for your solution! can you provide some explanation of the border of each loop? and why you pick them... the formula is easy to understand, but I'm a little bit confused about those loop

    THX!!


  • 0
    D

    @macctown The two for loops actually iterate one matrix in a special way. Since dp[i][j] has two dimensions i and j, then it forms a matrix. You need to imagine that it is a matrix. Our target is the top-right corner. In order to achieve our target, we have to calculate all its predecessors first. The base cases are actually the diagonal of the matrix. That's why I use jminusi (j - i) as 1 first. Then calculate the diagonal one by one.

    The key is: imagine it as a matrix, and we are filling the diagonal one by one!


  • 0

    @cdai very clean name, thanks


  • 0

    What's the difference between a bottom-up DP and a top-down DP?(I saw bottom-up solution and assume there is a top-down one). Thanks for any explanantion.


  • 1
    N

    @Tōsaka-Rin In top-down DP you only solve the sub-problems needed for the current problem and store the answers of the subproblems. You don't end up solving all of the possible subproblems.

    In bottom-up DP you first solve all of the possible subproblems at the lowest level, then use them to solve the subproblems at higher levels, and so on till you solve the problem.

    Practically, top-down is usually a recursive solution with a check to see if the problem is solved before, and so avoid solving it. Bottom-up up is iterative and it is easier to analyze its time and space complexity.


  • 0

    @nrl Thank you for explaining! I will write down your explanation.


  • 0
    T

    very clean explanation!
    marvelous!


  • 0
    M

    The equation for the DP is seems pretty complex. Even after drawing the 2D grid with various examples, the equation does not seem very intuitive. How did you guys think through the problem and arrive at this DP equation? I understand the idea of minimax and I completely understand how this guessing game works.

    Ex:
    "Math.min(dp[i][j], k + Math.max(dp[i][k - 1], dp[k + 1][j]))"

    dp[i][k-1] and dp[k+1][j] are (often) nowhere near each other in the DP grid. How did you come to the conclusion to use these values for the equation?


Log in to reply
 

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