LeetCode - Complete Knapsack Problems

Medium

322. Coin Change 518. Coin Change II 279. Perfect Squares 377. Combination Sum IV

完全背包基本概念

完全背包的核心是：每個物品可以被使用無限次

coins 可以重複使用
perfect square 可以重複使用
nums 裡的數字也可以重複拿來組合 target

常見寫法：

for(auto item: items){
    for(int j = item; j <= target; ++j){
        dp[j] = ...
    }
}

因為物品可以重複使用，所以容量通常從小到大更新

我的另一篇文章有解說各種背包問題的思路，底家 XD：

Algorithm - DP Knapsack

322. Coin Change

題目

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2

Input: coins = [2], amount = 3
Output: -1

Example 3

Input: coins = [1], amount = 0
Output: 0

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

解題思路

這題是完全背包
每種 coin 都可以使用無限次

DP 定義：
- dp[j]：湊出金額 j 需要的最少硬幣數
初始化：
- dp[0] = 0
- 湊出金額 0 不需要任何硬幣
- 其他位置初始化成 INF
因為每種 coin 可以重複使用
- 所以 j 從小到大更新
狀態轉移：
- 使用目前的 coin
- dp[j] = min(dp[j], dp[j-coin] + 1)
如果最後 dp[amount] == INF
- 代表無法湊出 amount
- 回傳 -1
否則回傳：
dp[amount]

Solution Code

Time Complexity
O(coins.length × amount)

Space Complexity
O(amount)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        const int INF = 1e9;
        vector<int> dp(amount+1, INF);

        dp[0] = 0;
        
        for(auto coin: coins){
            for(int j = coin; j <= amount; ++j){
                dp[j] = min(dp[j], dp[j-coin] + 1);
            }
        }
        return (dp[amount] == INF) ? -1 : dp[amount];
    }
};

518. Coin Change II

題目

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:

5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

Example 2

Input: amount = 3, coins = [2]
Output: 0

Example 3

Input: amount = 10, coins = [10]
Output: 1

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000

解題思路

這題是完全背包
每種 coin 都可以使用無限次

DP 定義：
- dp[j]：湊出金額 j 的組合數
初始化：
- dp[0] = 1
- 湊出金額 0 有一種方法，就是什麼都不選
因為每種 coin 可以重複使用
- 所以 j 從小到大更新
這題是求組合數
- 所以外層先枚舉 coin
- 內層再枚舉金額
- 這樣可以避免順序不同但內容相同的組合被重複計算
狀態轉移：
- dp[j] += dp[j-coin]
最後答案為：
dp[amount]

Solution Code

Time Complexity
O(coins.length × amount)

Space Complexity
O(amount)

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<unsigned int> dp(amount+1, 0);

        dp[0] = 1;

        for(int coin: coins){
            for(int j = coin; j <= amount; ++j){
                dp[j] += dp[j-coin];
            }
        }
        return dp[amount];
    }
};

279. Perfect Squares

題目

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Constraints

1 <= n <= 10^4

解題思路

這題是完全背包
每個 perfect square 都可以重複使用

可以把每個 perfect square 當成一種物品
- 1
- 4
- 9
- 16
- …
DP 定義：
- dp[j]：湊出數字 j 需要的最少 perfect square 數量
初始化：
- dp[0] = 0
- 其他位置設成 INF
先枚舉 num
- 如果 num 是 perfect square
- 就用它來更新 dp
因為每個 perfect square 可以重複使用
- 所以 j 從小到大更新
狀態轉移：
- dp[j] = min(dp[j], dp[j - num] + 1)
最後答案為：
dp[n]

Solution Code

Time Complexity
O(n × n)

Space Complexity
O(n)

class Solution {
public:
    int numSquares(int n) {
        const int INF = 1e9;
        vector<int> dp(n+1, INF);

        dp[0] = 0;

        for(int num = 1; num <= n; ++num){
            int x = sqrt(num);
            if(x * x == num){
                for(int j = num; j <= n; ++j){
                    dp[j] = min(dp[j], dp[j - num] + 1);
                }
            }
        }

        return dp[n];
    }
};

377. Combination Sum IV

題目

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1

Input: nums = [1,2,3], target = 4
Output: 7
Explanation: The possible combination ways are:

(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Example 2

Input: nums = [9], target = 3
Output: 0

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000

解題思路

這題是完全背包
每個 num 可以重複使用

但這題比較特別，是求排列數
不同順序會被當成不同答案

DP 定義：
- dp[j]：湊出總和 j 的排列數
初始化：
- dp[0] = 1
- 湊出 0 有一種方式，就是什麼都不選
因為這題順序不同也算不同組合
- 所以外層先枚舉 target
- 內層再枚舉 nums
狀態轉移：
- 如果 j >= num
- 則可以把 num 接在後面
- dp[j] += dp[j - num]
最後答案為：
dp[target]

Solution Code

Time Complexity
O(nums.length × target)

Space Complexity
O(target)

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target+1, 0);

        dp[0] = 1;

        for(int j = 1; j <= target; ++j){
            for(auto num: nums){
                if(j >= num) dp[j] += dp[j - num];
            }
        }
        
        return dp[target];
    }
};

Conclusion

完全背包的重點是每個物品可以使用無限次

如果是求最少數量
- 用 min
- 例如 322. Coin Change、279. Perfect Squares
如果是求方法數
- 用 +=
- 例如 518. Coin Change II、377. Combination Sum IV
如果是求組合數
- 外層枚舉物品
- 內層枚舉容量
如果是求排列數
- 外層枚舉容量
- 內層枚舉物品

最重要的是更新方向：
完全背包因為物品可以重複使用，容量通常從小到大更新