代码随想录算法训练营第四十八天 | 70. 爬楼梯（进阶）、322. 零钱兑换、279.完全平方数

70. 爬楼梯（进阶）

代码随想录

解题思路

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

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

2.递推公式

dp[j] += dp[j - nums[i] ] 装满背包有多少种方法一般用这个

3.遍历顺序

完全背包，且是排列，21和12是不同的方法，因为先遍历背包，再遍历物品，且都是正序

4.初始化

下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的

#include <bits/stdc++.h>
using namespace std;

int climb(int n, int m)
{
    if(n==1) return 1;
    std::vector<int> dp(n+1,0) ;
    dp[0] = 1;
    dp[1] = 1;
    for(int j=2; j<=n ; j++)
    {
        for(int i=1 ; i<= m ; i++)
        {
            if(j>=i)
            dp[j] += dp[j-i];
        }
    }
    return dp[n];
}

int main()
{
    int n,m;
    std::cin >> n >> m;
    std::cout << climb(n,m) << std::endl;
    return 0;
}

322. 零钱兑换

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili

代码随想录

解题思路

1. dp[j] 装满容量为j的背包，最少物品为dp[j]

2.递推公式

dp[j] = min(dp[j - coins[i] ] + 1 , dp[j] ) 取一个最小的，这个背包问题的典型递推公式是很像的

3.初始化

dp[0] = 0;

非零下标初始值为一个最大值，INT_MAX，保证dp[j]的值不会被覆盖

4.遍历顺序

求的是最小数，因此先物品再背包，和背包再物品是一样的

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        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.完全平方数

视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili

代码随想录

解题思路

1. dp[j] 装满容量为j 的正整数的最少完全平方数是dp[j]

2.递推公式

求的是最小值，因此min(dp[j] , dp[j - i*i] + 1)

3.初始化

dp[0] =0;

非零标为最大值，否则会覆盖最大值

4.遍历顺序

因为我们求的都是最少的元素，因此物品背包没有顺序，可以颠倒

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for(int i=1 ; i<=n ; i++)   //先物品，再背包
        {
            for(int j = i*i ; j<=n ; j++)
            {
                if(dp[j-i*i]!=INT_MAX)
                dp[j] = min(dp[j] , dp[j - i*i] + 1);
            }
        }
        return dp[n];
    }
};