day45|● 70. 爬楼梯（进阶）● 322. 零钱兑换 ● 279.完全平方数

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

70. 爬楼梯完全背包

1.代码

class Solution {
public:
    int climbStairs(int n) {
    vector<int>nums;
    vector<int>f(n + 1);
     f[0] = 1;
     for (int i = 0; i <= n; i++) {
         for (int j = 1; j <= 2; j++) {
             if (i >= j) f[i] += f[i - j];
         } 
     }
     return f[n];
    }
};

2.递归五部曲

1.确定dp数组和其下标的含义

题目所求是爬到楼梯顶的方案数f[i]就是爬到i层的方案数。f[n]就是爬到楼顶的方案数

2.确定递推公式

题目所求是方案数如f[i]方案数就是所有可以到达i的方案数相加比如可以走1步和2步f[i] = f[i - 1] + f[i - 2] + f[i - 3] +......所以遍历到这个物品时候就可以加入到达这个背包的方案数了

f[i] += f[i - nums[j]]

3.初始化

由递推公式可知没有可以叠加的值所以必须初始化f[0]=1

4.确定遍历顺序

因为是求排列数说明顺序不同也是一种方案所以需要第一层for循环遍历背包让背包来筛选物品第二层是遍历物品就是遍历台阶因为台阶只有两种完全可以用变量来代替

5.举例说明dp公式

距离前面几个代入dp公式看一下正确不正确

322. 零钱兑换

1.代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
         vector<int>f(amount + 1, INT_MAX);
         f[0] = 0;
         for (int i  = 0; i < coins.size(); i++) {
             for (int j = coins[i]; j <= amount; j++) {
                if (f[j - coins[i]] < INT_MAX - 1) f[j] = min(f[j], f[j - coins[i]] + 1);
             }
         }
         if (f[amount] == INT_MAX) return -1;
         return f[amount];
    }  
};

2.递归五部曲

1.确定dp数组和下标的含义

题目是凑成总金额所需的 最少的硬币个数所以dp[j]就是求出凑成钱数j的最小硬币个数

2.确定递推公式

每次凑足总金额j - coins[i]最小个数时f[j - coins[i]],那么只要加上这个硬币就可以得到dp[i],所以求f[j - coins[i]]+1的最小值就是dp[j]的结果相当于遍历所有类型的硬币加上这个硬币的最小硬币个数

dp[j] = min(dp[j], dp[j - nums[i]] + 1)

3.初始化

一开始全部都设置为int的最大值因为是求最小值第一个值不能为最大值因为这样不符合公式的推导f[0]=0符合凑出0元需要的硬币数

4.遍历顺序

第一层遍历物品第二层顺序遍历背包为了重复选择硬币。因为是求组合数所以是这样的

5.举例前几个证明dp数组

279. 完全平方数

1.代码

class Solution {
public:
    int numSquares(int n) {
        vector<int>f(n + 1, INT_MAX);
        f[0] = 0;
        for (int i = 1; i*i <= n; i++) {
            for (int j = i*i; j <= n; j++) {
                f[j] = min(f[j], f[j - i*i] + 1);
            }
        }
        return f[n];
    }
};