代码随想录算法训练营第36期DAY46

DAY46

完全背包

在闫氏DP法里学过：第i个物品选k个，纸质直至不能选，k从0开始取。就有递推式了。

代码随想录的视频也看了。

518零钱兑换ii

注意与 目标和 那题区分开。

完全背包问题，正向遍历背包容量，就能实现“多次取”

1. class Solution {
2. public:
3.     int change(int amount, vector<int>& coins) {
4.         vector<int> dp(amount+1);
5.         dp[0]=1;
6.         for(int i=0;i<coins.size();i++){
7.             for(int j=coins[i];j<=amount;j++)
8.             dp[j]+=dp[j-coins[i]];
9.         }
10.         return dp[amount];
11.     }
12. };

377组合总和iv

1. class Solution {
2. public:
3.     int combinationSum4(vector<int>& nums, int target) {
4.         vector<int> dp(target+1);
5.         dp[0]=1;
6.         for(int i=0;i<=target;i++){
7.             for(int j=0;j<nums.size();j++){
8.                 if(i>=nums[j]&&dp[i]<INT_MAX-dp[i-nums[j]])
9.                 dp[i]+=dp[i-nums[j]];
10.             }
11.         }
12.         return dp[target];
13.     }
14. };

晚些时候发新专栏，学习图神经网络。