代码随想录算法训练营 ---第四十五天

前言：

昨天的题做过之后，今天的题基本上都很简单，但是要注重一下细节。

第一题：

简介：

动态规划五部曲：

1.确定dp数组的含义

dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法

2.确定dp公式

i:可以看作本次的物品值

j:可以看作背包容量

dp[j] +=dp[j-i];

3.确定如何初始化dp数组

dp[0] = 1;

4.确定如何遍历数组

先遍历背包，再遍历物品（因为我们先迈一步再迈两步还是先迈两步再迈一步是有区别的）

 for(int j=0;j<=n;j++){
        for(int i=1;i<=m;i++){
            if(j-i>=0)
            dp[j] +=dp[j-i];
        }
    }

5.打印数组，看是否正确

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int palou(int m,int n){
    vector<int> dp(n+1,0);
    dp[0] = 1;
    for(int j=0;j<=n;j++){
        for(int i=1;i<=m;i++){
            if(j-i>=0)
            dp[j] +=dp[j-i];
        }
    }
    return dp.back();
}


int main(){
   int m,n;
   cin>>n>>m;
   cout<<palou(m,n);
   return 0;
}

第二题：

简介：

我认为本题的重点在于如何初始化dp数组，自己做时在那里吃了亏。

动规五部曲分析如下：

确定dp数组以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

2.确定递推公式递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); 如果放入就加一个金币，不放入就不加。

3.dp数组如何初始化首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;然后考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。

代码如下：

vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;

4.确定遍历顺序

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！

5.举例推导dp数组

322.零钱兑换

dp[amount]为最终结果。

代码实现：

    //dp[j]表示组成j 所需最少硬币个数
    int coinChange(vector<int>& coins, int amount) {
         vector<int> dp(amount+1,INT_MAX);
         dp[0]=0;
         for(int i=0;i<coins.size();i++){
             for(int j=coins[i];j<=amount;j++){
                  if (dp[j - coins[i]] != INT_MAX)
                  dp[j] =min(dp[j],dp[j-coins[i]]+1);        
             }
         }
         if(dp.back()==INT_MAX)return -1;
         else
         return dp.back();
    }

第三题：

简介：

本题和上一题十分相似，只不过我们在遍历时要注意完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？这样本题是不是就很清晰了。

代码实现：

先遍历背包，再遍历物品

int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) { // 遍历背包
            for (int j = 1; j * j <= i; j++) { // 遍历物品
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }

先遍历物品，再遍历背包

    int numSquares(int n) {
        if(n<4)return n;
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for(int i=1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
               dp[j] =min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp.back();
    }