LeetCode 70 爬楼梯 （进阶）

题目链接：https://leetcode.cn/problems/climbing-stairs/

题目描述：

爬到顶层需要n阶，每次可以走[1-m]阶，从问：爬到顶层有多少种方法?

思路：

• dp数组的含义

dp[j]代表爬到j阶有多少种方法

• 递推公式

本题是求装满背包有多少种方法，所以递推公式如下：

• 初始化

因为是累加的情况，所以

• 遍历方式

本题是排列问题，因为[1,1,2]和[1,2,1]显然不是同一种组合，所以外层for循环遍历背包，内层for循环遍历物品

代码：

class Solution {
public:int climbStairs(int n) {vectordp(n+1,0);dp[0] = 1;for(int j = 0; j <= n; j++){for(int i = 0; i <= m; i++){if(j >= i)dp[j] += dp[j - i];}}return dp[n];}
};

总结

爬楼梯的进阶版，和完全背包问题联系起来。

LeetCode 322 零钱兑换

题目链接：https://leetcode.cn/problems/coin-change/

思路：

• dp数组的含义

dp[j]代表金额为j时的最小硬币个数

• 递推公式

本题是求装满背包时最小重量多少，所以递推公式如下：

• 初始化

本题显然dp[0]=0，但是因为是求的最小值，所以dp数组的其余值要是最大值。如果初始化为0，那么结果会受到0的影响。

• 遍历方式

本题求的是最小硬币个数，所以组成的集合并不关心，两种循环方式都可以。

代码：

class Solution {
public:int coinChange(vector& coins, int amount) {vectordp(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[amount] == INT_MAX)   return -1;return dp[amount];}
};

总结

完全背包的应用题，相对简单。

LeetCode 279 完全平方数

题目链接：https://leetcode.cn/problems/perfect-squares/

思路：

• dp数组的含义

dp[j]代表和为j时的完全平方数的最少数量

• 递推公式

本题是求装满背包时最小重量多少，所以递推公式如下：

• 初始化

本题显然dp[0]=0，但是因为是求的最小值，所以dp数组的其余值要是最大值。如果初始化为0，那么结果会受到0的影响。

• 遍历方式

本题求的是完全平方数的最少数量，所以组成的集合并不关心，两种循环方式都可以。

代码：

class Solution {
public:int numSquares(int n) {vectordp(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[n];}
};

总结

相对简单。

今日总结：

今天的题目是完全背包的应用题，相对简单。