Greedy + dp; c++; O(n(log(n)))


  • 0
    J

    one observation:
    the pick at the end should always be n - (2^k - 1);
    We can prove this with some tricky math....

    class Solution {
    public:
        int getMoneyAmount(int n) {
            int re[n+1];
            int count[n+1];
            re[0] = 0; count[0] = 0;
            re[1] = 0;count[1] = 0;
            re[2] = 1;count[2] = 1;
            re[3] = 2;count[3] = 1;
            re[4] = 4;count[4] = 2;
            
            for(int i = 5; i <= n; i++)
            {
                int mintmp = INT_MAX;
                int sum = 0;
                for(int j = 2; j <= i; j*=2)
                {
                    
                    int tmp = max(i-j+1 + sum, re[i-j] + i-j+1);
                    sum+=i-j+1;
                    if(tmp < mintmp)
                    {mintmp = tmp;}
                    
                    
                }
                re[i] = mintmp;
            }
            
            return re[n];
            
            
            
            
        }
    };
    

  • 1
    D

    @jersey Could you let us know the math behind the scene? :)


  • 1

    @jersey Your solution fails for example n=124. Your output is 557, correct is 555.


  • 2
    X

    I don't think there is any trick for this problem, you have to enumerate all.

    In DP, I tried to calculate cost for range [1+x, n+x] from [1, n] but failed; then I realized there is no trick, have to enumerate...


  • 0

    @StefanPochmann Thanks, added this test case.


  • 0
    T

    @xing2 same here. I tried maintaining how many counts are used in [1..n] so [1+x,n+x] would be x*count + [1..n] with the same selection. But after failing test case 17 it took me hours to realize the selection of numbers may change...


  • 0
    X

    @theOtherWC :)

    I did the same thing. But I want to blame the judger :) because my first version, which is finished within 2 minutes, correct but using top-down DP, failed due to TLE. Then I thought there must be relationship between [1+x, n+x] and [1, n] (and my instinct tell me that is wrong!) The intuition is simple: when you have larger numbers (with x), you want to use less times to guess, however it is super hard to provide a counter example.


  • 0
    Y

    I did exactly the same thing yesterday however failed at n = 124. The correct is 555 and ours 557. And I don't know where the problem was yet.


  • 1

    @xing2 Well depends on what you mean with "relationship". But here's a small example showing it's at least not trivial: The range [1,8] has a best worst case of $12, namely $5+$7. And for the range [1001,1008], which is the same range but 1000 higher, it's $3009. Namely $1005+$1003+$1001. It isn't $1005+$1007 because that's one fewer guess, and up there, the number of guesses is most important.


Log in to reply
 

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