本文主要是介绍代码随想录算法训练营day45|第九章 动态规划part07：70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
70. 爬楼梯 （进阶）
这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍
代码随想录
普通的完全背包求排列数问题。
#include <bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;vector<int> dp(n+1,0);dp[0]=1;for(int i=1;i<n+1;i++){for(int j=1;j<=m;j++){if(i>=j) dp[i]+=dp[i-j];}}cout<<dp[n]<<endl;return 0;
}322. 零钱兑换
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
这句话结合本题 大家要好好理解。
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili
代码随想录
这道题本质上是完全背包求最大值的变种，所以自然无关背包和硬币的遍历顺序，主要是初始化和递推公式比较新颖。因为是求最小硬币数量，所以递推公式自然是 dp[j] = min(dp[j - coins[i]] + 1, dp[j]) ，而如果要这么求dp数组的值，势必要将每个dp数组的值初始化为INT_MAX，而因为最终还是要改写dp数组的值的（无论哪个总面值，想要得到最小硬币数，就必须利用过dp[0]的值，这时得到的结果必然是1），所以dp[0]需要初始化为0，理解当然是很容易，0元就是0个硬币。注意在利用这个递推公式的时候，要判断dp[j - coins[i]]是否已经被改写（也就是能否找到硬币组成这个面值），如果没有改写，就不能进入计算。还要注意一点，如果dp[amount]==INT_MAX，那就证明没有合适的方法能组成这个总面值，按要求返回-1即可。
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 - coins[i]]是初始值则跳过dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if (dp[amount] == INT_MAX) return -1;return dp[amount];}279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili
代码随想录
这道题和上一道大差不差。特别的是这道题不需要在套用递推公式的时候判断当前要利用的dp[j-i*i]是否有解了，这是因为当i=1时对dp数组的遍历已经将整个数组初始化完毕了，最先利用的值是dp[0]，在这次遍历数组中利用的值均恰好是前一个dp数组的值，故而就一个个都有了解。
还有一点比较特别的是这道题对于平方数的处理，我自己是用了开平方法函数，但是文章里面是直接用 i * i 来表示平方数，这样快很多，还很简便。
int numSquares(int 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 - i * i] + 1, dp[j]);}}return dp[n];}这篇关于代码随想录算法训练营day45|第九章 动态规划part07：70. 爬楼梯 （进阶）、322. 零钱兑换、279.完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
