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

感觉要没书读了。。

DAY48

卡码网57爬楼梯

复习一遍：背包容量在外层循环，物品在内层循环，则为排序数；

物品在外层循环，背包容量在内层循环，则为组合数。

1. #include<iostream>
2. #include<vector>
3. using namespace std;
4. int main(){
5.     int n,m;
6.     scanf("%d%d",&n,&m);
7.     vector<int> dp(n+1);
8.     dp[0]=1;
9.     vector<int> nums(m,1);
10.     int count=1;
11.     for(int &n:nums)n=count++;
12.     //先背包，再物品
13.     for(int i=0;i<=n;i++){
14.         for(int j=0;j<nums.size();j++){
15.         if(i>=nums[j])
16.         dp[i]+=dp[i-nums[j]];
17.         }
18.     }
19.     cout<<dp[n]<<endl;
20.     return 0;
21. }

322零钱兑换

1. class Solution {
2. public:
3.     static bool mycmp(int &a,int &b){
4.         return a>b;
5.     }
6.     int coinChange(vector<int>& coins, int amount) {
7.         sort(coins.begin(),coins.end(),mycmp);
8.         if(amount==0) return 0;
9.         vector<int> dp(amount+1,INT_MAX);
10.         dp[0]=0;
11.         for(int i=0;i<coins.size();i++){
12.             for(int j=coins[i];j<=amount;j++){
13.                 //要用本层已被覆盖的值，那么要跳过没覆盖的值 if
14.                 if(dp[j-coins[i]]!=INT_MAX){
15.                     dp[j]=min(dp[j],dp[j-coins[i]]+1);
16.                 }
17.             }
18.         }
19.         if(dp[amount]==INT_MAX) return -1;
20.         return dp[amount];
22.     }
23. };

860柠檬水找零

1. class Solution {
2. public:
3.     bool lemonadeChange(vector<int>& bills) {
4.         int five=0,ten=0;
5.         for(int i=0;i<bills.size();i++){
6.             if(bills[i]==5){
7.                 five++;
8.             }
9.             else if(bills[i]==10){
10.                 if(five<=0) return false;
11.                 ten++;
12.                 five--;
13.             }
14.             else{
15.                 if(ten>0&&five>0) five--,ten--;
16.                 else if(five>2) five-=3;
17.                 else return false;
18.             }
19.         }
20.         return true;
21.     }
22. };

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=0;j<=amount;j++){
8.                 if(j>=coins[i])
9.                 dp[j]+=dp[j-coins[i]];
10.             }
11.         }
12.         return dp[amount];
13.     }
14. };

279完全平方数

1. class Solution {
2. public:
3.     int numSquares(int n) {
4.         int uper=sqrt(n);
5.         vector<int> dp(n+1,INT_MAX);
6.         vector<int>nums(uper+1,1);
7.         int p=1;
8.         for(auto &num:nums) num=p*p,p++;
9.         dp[0]=0;
10.         for(int i=0;i<nums.size();i++){
11.             for(int j=nums[i];j<=n;j++){
12.                 if(dp[j-nums[i]]!=INT_MAX)
13.                 dp[j]=min(dp[j],dp[j-nums[i]]+1);
14.             }
15.         }
16.         return dp[n];
17.     }
18. };

节省空间的写法：

1. class Solution {
2. public:
3.     int numSquares(int n) {
4.         int uper=sqrt(n);
5.         vector<int> dp(n+1,INT_MAX);
6.         dp[0]=0;
7.         //遍历背包，再物品
8.         for(int i=0;i<=n;i++){
9.             for(int j=1;j*j<=i;j++){
10.                 dp[i]=min(dp[i],dp[i-j*j]+1);
11.             }
12.         }
13.         return dp[n];
14.     }
15. };

遍历顺序不一样时，需要注意dp里面的符号。