[LeetCode] 518. Coin Change 2

https://leetcode.com/problems/coin-change-2/?tab=Description

Solution:
This is one of the classical questions for dynamic programming. And it belongs to the complete 01 knapsack problem. Let's suppose dp[i][j] represents the number of ways to make up amount of j with 1 to ith coins. Then when we move onto the next coin, we have to make choice. If the denomination of the next coin larger than j, then we cannot use it; if smaller, we can use it. Thus, the transition formula is:
                       dp[i+1][j] = dp[i][j] + dp[i+1][j-v[i+1]]
The first term means the way without using the (i+1)th coin; and the second one means the way with using the (i+1)th coin. This equation can be further simplified into an one-dimensional vector,
                      dp[j] = dp[j] + dp[j-v[i+1]]
                  or, dp[j] += dp[j-v[i+1]]
 See code below.

Code:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(auto a:coins){
            for(int i=1; i<=amount; ++i){
                if(i>=a) dp[i] += dp[i-a];
            }
        }
        return dp[amount];
    }
};

[leetcode] 322. Coin Change

https://leetcode.com/problems/coin-change/?tab=Description

Solution:
A good question for dynamic programming. It also belongs to 01 knapsack problem. Let's suppose dp[i] represents the minimum coins needed to make up the amount, then the transition formula will be
              dp[i] = min(dp[i], dp[i-c[j]] + 1),   c[j] <= i;

Some details for implementation:
1): dp[0] can be set as 0; since it means the minimum number of coins needed for 0 is 0, which is legal based on the definition of dp[0];
2): All the rest dp[i] can be set (as amount + 1) since if there's at least one way to make up the amount, then minimum coins needed will be no larger than amount itself, because the worst situation (or the largest) is there are coins with 1 as the denomination and it is the only way to make up the amount.
3): to speed up a little bit, we can sort the coins. For coins bigger than i, we can just ignore them.

Code:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount == 0) return 0;
        if(coins.empty()) return -1;
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;
        sort(coins.begin(), coins.end());
        for(int i=1; i<=amount; ++i){
            for(int j=0; j<coins.size(); ++j){
                if(i>=coins[j]){
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                }
                else break;
            }
        }
        return dp[amount]==amount + 1?-1:dp[amount];
    }
};    

474. Ones and Zeroes

https://leetcode.com/problems/ones-and-zeroes/

solution:
这是个2维01背包问题 (two-D 0-1 Knapsack Problem). 所以不再啰嗦了， 如果第一次见到此类问题，就google "Knapsack Problem".

代码：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //two-dimentional 0-1 knapsack problem.
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(auto s:strs){
            int count1 = 0, count2 = 0; // count1 for '0' and count2 for '1';
            for(auto c:s){
                if(c=='0') ++count1;
                else ++count2;
            }
            for(int i=m; i>count1-1; --i){
                for(int j=n; j>count2-1; --j){
                    dp[i][j] = max(dp[i][j], dp[i-count1][j-count2] + 1);
                }
            }
        }
        return dp[m][n];
    }
};