70.爬楼梯（进阶）
分析：基本动态规划转换为完全背包，因为1、2 两种上楼梯方式是无限选择的
思路：
- 1. j 表示 容量为 j 时，装满有dp[j]种方法
- 2. dp[j]+=dp[j-nums[i]]
- 3. 初始化 dp[0]=1,dp[1]=1
- 4. 遍历顺序：外层遍历容量 内层遍历物品
class Solution {
public:int climbStairs(int n) {vector<int>dp(n+1,0);dp[0]=dp[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=2;j++){dp[i]+=dp[i-j];}}return dp[n];}
};
322.零钱兑换
分析：硬币无限，组合成金额 -> 完全背包（组合）
思路：
- 1.dp存储：金额为 j 时，有 dp[j] 种方法
- 2.dp[j]=min(dp[j],dp[j-coins[i]]+1)
- 3.dp[0]=0
- 4.遍历顺序：外层遍历硬币，内层遍历容量
class Solution {
public: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[amount]==INT_MAX) return -1;return dp[amount];}
};
279.完全平方数
思路：
-
1.dp存储： 容量为 j 时，装满的最少使用数字为dp[j]种方法
-
2.dp[j]=min(dp[j],dp[j-i*i]+1)
-
3.初始化：dp[0]=0 INT_MAX
-
4.遍历顺序：外层遍历数字，内层遍历容量
class Solution {
public: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],dp[j-i*i]+1);}}return dp[n];}
};
