For input = 18, why is solution not 39 but 42?


  • 0
    J

    I use divide and conquer. Basically, loop through 1 to 18 and use each as the divider. Then the left and right part become subproblems. The outer loop computes and stores the optimal cost and #oflookup for values smaller than 18.

    For example, my code use the bold italic as seperator:
    1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18

    The code computes
    left = getMoneyAmount(6)
    right = getMoneyAmount(11) + #oflookup(11) * 7 (seperator value)
    Since right > left, and right < all other possible solution, 7 is taken as the seperator.

    Then 15 and 17 are taken as the seperator.
    8,9,10,11,12,13,14,15,16,17,18
    16,17,18

    So 7 + 15 + 17 = 39.

    Here's the code:

    class Solution {
    public:
        unordered_map<int,pair<int,int>> dp; //cost, #oflookup
        int getMoneyAmount(int n) {
            dp[1] = make_pair(0,0);
            dp[2] = make_pair(1,1);
            dp[3] = make_pair(2,1);
            dp[4] = make_pair(4,2);
            if(n < 4) return dp[n].first;
            int mid = 3;
            for(int r = 5; r <= n; r++){
                dp[r] = make_pair(INT_MAX,INT_MAX);
                for(int mid = 1; mid <= r; mid++){
                    int left = mid + dp[mid - 1].first;
                    int right = mid + dp[r - mid].first + dp[r - mid].second * mid;
                    int leftcount = 1 + dp[mid - 1].second;
                    int rightcount = 1 + dp[r - mid].second;
                    if(left > right && dp[r].first > left){
                        dp[r] = make_pair(left,leftcount);
                        cout << r << " left: " << left << " " << leftcount << " " << mid << endl;
                    } else if(left <= right && dp[r].first > right) {
                        dp[r] = make_pair(right,rightcount);
                        cout << r << " right: " << right << " " << rightcount << " " << mid << endl;
                    }
                }
            }
            return dp[n].first;
        }
    };
    

  • 1

    What if the number is larger than 7 but smaller than 15?


  • 0
    J

    @StefanPochmann No I multiply #of lookup for [1001...1010] by the divider value of say 1000 to account for the offset.


  • 1

    @johnwyz88 Yeah I realized that and changed my comment.


  • 0
    J

    @StefanPochmann It will take 12, then 9 then 6... Add up to 49.. Thanks for pointing that out!! I should multiply the divider by sum of the #oflookup instead of just the initial one.


  • 0

    @johnwyz88 I think you indirectly do add them all up. The real problem is that your basic assumption is wrong, that same-size ranges are somehow equivalent and you just need to adjust somewhat like you do. For example, for the range 1..8, the worst case is having to pay $12. But for the range 101..108, the worst case is having to pay $309. Try finding optimal strategies for these two ranges and figuring out why they differ.


  • 0
    J

    @StefanPochmann Yeah I realize that the previously calculated value cannot be used because the side with more look up could become more expensive. It's best to compute the ranges recursively instead.


Log in to reply
 

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