JLUVicent

70爬楼梯&322零钱兑换&279完全平方数

 
  • 2023年 03月31日
  • 0 阅读

day45

70.爬楼梯

题目连接：70. 爬楼梯

解题思路：参考

之前做过的爬楼梯题目，这次可以用完全背包来完成，动态规划五部曲

1.确定dp[j]及下标含义：容量为j的背包最多有多少种方法能装满

2.确定递推公式：dp[j] += dp[j-nums[i]];

3.初始化：dp[0] = 1；如果初始化为0则之后全为0

4.确定遍历顺序：类似排列问题先遍历背包在遍历物品

5.打印dp数组

class Solution {
public:
    int climbStairs(int n) {
        // 按照完全背包理论处理
        vector<int> nums = {1,2};
        vector<int> dp(n+1,0);
        dp[0] = 1;
        for( int j = 0; j <= n; j++){
            for( int i = 0; i < nums.size(); i++){
                if( j >= nums[i]){
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[n];

    }
};

//复习之前的版本
class Solution {
public:
    int climbStairs(int n) {
        // // 按照完全背包理论处理
        // vector<int> nums = {1,2};
        // vector<int> dp(n+1,0);
        // dp[0] = 1;
        // for( int j = 0; j <= n; j++){
        //     for( int i = 0; i < nums.size(); i++){
        //         if( j >= nums[i]){
        //             dp[j] += dp[j - nums[i]];
        //         }
        //     }
        // }
        // return dp[n];

        if( n <= 2) return n;
        int dp[2];
        dp[0] = 1;
        dp[1] = 2;
        int sum ;
        for( int i = 3; i <= n; i++){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

322.零钱兑换

题目链接：322. 零钱兑换

解题思路：参考 视频

第一次做的时候根据之前的思路，直接ac了，稀里糊涂

递归五部曲：

1.dp[j]及下标含义：装满容量为j的背包所需的最少的硬币数量

2.确定递推公式：dp[j] = min( dp[j],dp[j-coins[i]]+1)

3.初始化：dp[0] = 0;其他需要用min来覆盖，因此初始化为INT_MAX

4.遍历顺序：组合问题，先遍历物品再遍历背包

5.打印dp数组

322.零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,0);
        dp[0] = 0;
        for( int i = 1; i <= amount; i++){
            dp[i] = INT_MAX;
        }
        for( int i = 0; i < coins.size(); i++){
            for( int j = coins[i]; j <= amount; j++){
                if(dp[j-coins[i]] < INT_MAX - 1)//注意这里有个临界条件需要比较，也就是保证其不能越界
                dp[j] = min(dp[j],dp[j-coins[i]] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

先遍历物品，再遍历背包，求组合数

先遍历背包，再遍历物品，求排列数

279.完全平方数

题目链接：279. 完全平方数

解题思路：参考 视频

和上一题一模一样

还是相同的套路，第一遍直接ac，本题要注意如何确定物品数组，题目已经给出了范围，因此直接求即可。

class Solution {
public:
    int numSquares(int n) {
        vector<int> nums(101,0);
        for( int i = 1; i <= 100; i++){
            nums[i] = i*i;
        }
        vector<int> dp(n+1,0);
        dp[0] = 0;
        for( int i = 1; i <= n; i++){
            dp[i] = INT_MAX;
        }
        for( int i = 0; i < nums.size(); i++){
            for( int j = nums[i]; j <= n; j++){
                if( dp[j - nums[i]] < INT_MAX - 1)
                dp[j] = min( dp[j] ,dp[j - nums[i]] + 1);
            }
        }
        return dp[n];

    }
};
// 数组有点多余，还增加了时间和空间复杂度，直接用数值替代即可
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for( int i = 0; i <=100; i++){
            for( int j = i*i; j <= n; j++){
                if( dp[j - i*i] < INT_MAX - 1)
                dp[j] = min( dp[j] ,dp[j - i*i] + 1);
            }
        }
        return dp[n];

    }
};
搜索