C++ O(n*target) DP solution with idea sharing, similar to coin change problem


  • 2

    I think it's quite similar to coin change problem. We just need to regard nums as a set of coins with different denominations and target is the amount of money. Coins are unlimited. We should find the first smallest amount of money for which we can make change and set the initial number of coin combination as 1 for it. Then we just need to record the number of combinations we can make change for a specific amount of money and develop a DP algorithm for this question. The complexity is O(n*target), n is the size of nums.

    Update(for fun):
    If you can solve this question with the idea mentioned above, you can also try to solve this one :)
    http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            if (nums.size() == 0 || target <= 0) return 0;
            vector<int> dp(target + 1, 0);
            dp[0] = 1;
            for (int i = 1; i <= target; ++i) 
                for (int j = 0; j < nums.size(); ++j) 
                    if (nums[j] <= i) dp[i] += dp[i - nums[j]];
            return dp[target];
        }
    };
    

  • 0
    J

    @haruhiku I really cannot figure out the difference for this problem and 'coin change problem'... Could you say something more on that?


  • 0

    @justin.deng For this question with the restricted conditions, yes you may think it is almost the same as coin change problem because both target value and the number set are non negative. However, when you look at the follow up question (if negative numbers are allowed), then my solution will fail. Actually it is better to consider all numbers will be tested in this question and figure out a general solution to both negative and non negative numbers. At this point, you will see the difference.


  • 0
    H

    @haruhiku How to solve the general problem? If we have mix of positive and negative numbers, and assume every number can be used once. I know it can be solved by DFS approach. But does DP still work here?


Log in to reply
 

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