Simple DP solution with explanation~~


  • 129
    B

    For each number x in range[i~j]
    we do: result_when_pick_x = x + max{DP([i~x-1]), DP([x+1, j])}
    --> // the max means whenever you choose a number, the feedback is always bad and therefore leads you to a worse branch.
    then we get DP([i~j]) = min{xi, ... ,xj}
    --> // this min makes sure that you are minimizing your cost.

    public class Solution {
        public int getMoneyAmount(int n) {
            int[][] table = new int[n+1][n+1];
            return DP(table, 1, n);
        }
        
        int DP(int[][] t, int s, int e){
            if(s >= e) return 0;
            if(t[s][e] != 0) return t[s][e];
            int res = Integer.MAX_VALUE;
            for(int x=s; x<=e; x++){
                int tmp = x + Math.max(DP(t, s, x-1), DP(t, x+1, e));
                res = Math.min(res, tmp);
            }
            t[s][e] = res;
            return res;
        }
    }
    

    Here is a bottom up solution.

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

  • 0
    X

    Thanks for the solution!

    I had a similar idea. But the following doesn't work. (correct up to n = 61.)
    The difference between yours and mine is that I thought the

     table[k+1][j]
    

    in your

     int localMax = k + Math.max(table[i][k-1], table[k+1][j]);
    

    can be calculated as "above" in the following code. Why that is wrong?

    int getMoneyAmount(int n) {
        vector<int> amt(n+1, 0); // minimum money needed
        vector<int> cnt(n+1, 0); //minimum number of guesses needed
        
        for(int i=2; i<=n; i++) {
            amt[i] = INT_MAX;
            for(int j=i-1; j>=1; j--) {
                int above = amt[i-j]+j*cnt[i-j]; //money needed to handle [j+1, i]
                int below = amt[j-1]; //money needed to handle [1, j-1]
                if(amt[i]>j+max(above, below)) {
                    amt[i] = j+max(above, below);
                    cnt[i] = 1 +max(cnt[i-j], cnt[j-1]);
                }
                else if(amt[i]==j+max(above, below)){
                    cnt[i] = min(cnt[i], 1+max(cnt[i-j], cnt[j-1])); //prefer lower number to guess
                }
            }
        }
        return amt[n];
    }

  • 0
    X

    A simple example. What is the difference between

     t[1][15] 
    

    and

     t[101][115]
    

    I thought it's

     t[101][115] = t[1][15]+100*cnt[15] //number of guess to handle [1, 15].
    

    That is not true in many cases, can anyone point out why?


  • 3
    A

    @xipeace This is not correct. Imagine adding 10^10 instead of 100. There decreasing the maximum number of query is crucial, so the optimal solution is perfect binary search. When the value is small, however, you can sometimes do better than perfect binary search by asking a number larger than half first. You may have to ask more when the answer is smaller, but the cost per question is small.


  • 1
    C

    How to modify this code to answer this follow-up?

    As a follow-up, how would you modify your code to solve the problem of minimizing the expected loss, instead of the worst-case loss?


  • 0

    This is good


  • 0
    A

    I understand the logic quite a bit but one loop is still confusing to be . From my understanding we want to store the solution of from j to i so we loop on k by selecting a number k between i and j and calculate the cost of left and right parts. whatever is max we store it for table[i][j]. My confusion is why do we need to loop on i, why it cannot be 1 always? like for j=3 why should we have loop from i = j-1 to 0


  • 2
    Z

    @xipeace
    2 guesses for this:
    1 2 3 4 5 6 7 8 9 10
    3 + 5 + 7 < 9 + 7
    will not work for the following:
    11 12 13 14 15 16 17 18 19 20
    13 + 15 + 17 > 19 + 17


  • 12

    这是我隔壁老王,我骄傲!!!


  • 0
    J

    if at the end, DP return res, why is necessary to have " t[s][e] = res" ? Can someone explain ?


  • 1
    A

    @xipeace
    I tried to under this difference from a tree structure. The solution structure is actually a binary recursion tree: For t[1][15], the root is 12. left child is rooted t[1][11] and right child is rooted at t[13][15]. However, for t[101][115], the cost of this structure is no longer optimal, because the left tree has more levels, and for each level, you need to add an additional cost 100 to the subroot, which makes the cost in left subtree much larger than the right subtree.


  • 0
    D

    @jessica21 memorize results to avoid repeated computation.


  • 0
    D

    said in Simple DP solution with explanation~~:

    i+1==j

    The bottom-up approach is nice. Could you explain why we need to check i+1==j? Thanks


  • 8
    F

    @dukeforever It would be the case that you only have two coins to choose from. For example [5, 6], are you going to choose 5 or 6? Obviously you will choose 5, since it is smaller. That's why when i + 1 == j, dp[i][j] = i.


  • 0
    G

    thanks for sharing!


  • 0
    H

    I wrote a similar code with few base cases. However, I used a dictionary instead of a table to store previous results. I am not sure why my code is exceeding the time limit. Only difference between our code is that we lookup the value in different way. Your lookup O(1) and as far as I know, dictionary lookups in python are O(1). Can you please explain what am I doing wrong?

    class Solution(object):
        d = {}
        def getMoneyAmount(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n == 1:
                return 0
            if n == 2:
                return 1
            cost  = n * (n + 1) // 2 #this is the maximum cost, if each number is chosen sequentially
            for i in range(2, n):
                cost = min(cost,i+max(self.getMoneyAmount2(i + 1, n),self.getMoneyAmount2(1,i-1)))
            Solution.d[(1,n)] = cost
            return cost
    
        def getMoneyAmount2(self, low, high):
            if low >= high:
                return 0
            elif low + 1 == high:
                return low 
            elif low + 2 == high:
                return low + 1
            elif (low,high) in Solution.d:
                Solution.d[(low,high)]
            cost  = (low+high)*(high-low+1)//2
            for i in range(low + 1, high):
                cost = min(cost,i + max(self.getMoneyAmount2(i + 1, high),self.getMoneyAmount2(low, i-1)))
            Solution.d[(low,high)]=cost
            return cost

  • 0

    Thanks for sharing! The recursive solution is very concise!
    BTW, what the complexity should be? Since each position in "int[][] dp" be computed once, the time complexity is O(N^2), right?


  • 4
    L

    in the bottom up solution : for(int k=i+1; k<j; k++) why we need i+1 <= k < j, why we cannot choose k = i or k = j as a guess number in this case?


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

Log in to reply
 

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