LeetCode 热题100之动态规划1

🕗 发布于 2024-11-12 00:13 leetcode 动态规划算法

对于动态规划的问题，解题步骤有以下几部(总结为动态规划五部曲：参考代码随想录动态规划

确定dp数组以及下标的含义；
确定递推公式；
dp数组如何初始化；
确定遍历顺序；
举例推导dp数组

下面的解题思路分析都将从以上动规五部曲展开。

1.爬楼梯

在这里插入图片描述
思路分析：动规五部曲

dp[i]:达到i阶楼梯有i种方法；
递推公式;由于当前状态可以由前一种状态走一步到达也可以由前两的状态走两步到达，所以dp[i] = dp[i - 1] + dp[i - 2];
初始化：题目中n是正整数，所以初始化：dp[1] = 1,dp[2] = 2即可；
遍历顺序：因为要保证计算的时候所用的dp[i-1]和dp[i-2]是更新后的，所以要从前往后遍历；
打印dp数组（debug）：1，2，3，5，8…

具体实现代码（详解版）：

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1,0);

        if(n == 1) return 1;
        if(n == 2) return 2;

        dp[1] = 1,dp[2] = 2;//初始化

        for(int i = 3; i <= n ; i ++){
            dp[i] = dp[i - 1] + dp[i - 2];//递推公式
        }
        
        return dp[n];
    }
};

当然，实际上，我们只关心 dp[i-1] 和 dp[i-2]，因此可以将数组的空间复杂度从 O(n) 降到 O(1)，使用两个变量来存储最近的两个结果。

class Solution {
public:
    int climbStairs(int n) {
        int p = 0 ,q = 0 ,r = 1;
        for(int i = 1 ; i <= n ; i ++){
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

2.杨辉三角

在这里插入图片描述
思路分析：动规五部曲

dp数组：dp[i][j]表示杨辉三角第i+1行第j+1列的元素。其中i从0-numRows，j从0~i
递推公式：每行的第一个和最后一个元素是 1，其他元素是上一行相邻两个元素之和。所以递推公式为dp[i][j] = dp[i - 1][j] +dp[i - 1][j - 1]；
初始化当前行：dp[i][0] = 1,dp[i][i] = 1;
遍历顺序：由于是从上往下依次填充元素，所以应该从第0行从前往后遍历；
举例推导dp数组

[
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]

具体实现代码（详解版）：

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> dp(numRows);

        for(int i = 0 ; i < numRows ; i ++){
            //初始化当前行
            dp[i].resize(i + 1);
            dp[i][0] = dp[i][i] = 1;

            //计算中间元素：上一行相邻元素之和
            for(int j = 1 ; j < i ; j ++){
                dp[i][j] = dp[i - 1][j] +dp[i - 1][j - 1];//递推公式
            }
        }
        return dp;
    }
};

时间复杂度： $O(numRows^2)$
空间复杂度： $O(numRows^2)$ ，存储杨辉三角的所有元素

3.打家劫舍

在这里插入图片描述
思路分析：动归五部曲

dp[i]：表示抢劫到第i家的最大金额；
递推公式：这道题目可以分为两种情况
- 不抢第i家，则此时最大金额为dp[i - 1];
- 抢第i家，则此时最带金额为dp[i - 2] + nums[i],即加上 i 家的金额和不抢相邻的 i-1 家的最大金额；
- 最终递推公式：d[i] = max(dp[i - 1],dp[i - 2] + nums[i]);
初始化：dp[0]=nums[0],这是直接抢劫第一家；dp[1] = max(nums[0],nums[1]),是取第一家和第二家中较大的金额，因为你不能同时抢劫第一家和第二家。
遍历顺序：从前往后，因为后面的金额与前面的金额有关系，且确保是计算过的值参与后续的更新；
打印DP数组：可以debug

具体实现代码（详解版）：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();  // 获取nums数组的大小
        vector<int> dp(n);     // 创建一个dp数组，长度为n，用来保存到每个位置的最大抢劫金额

        // 边界条件：
        if (n == 0) return 0;  // 如果数组为空，返回0
        if (n == 1) return nums[0];  // 如果只有一个房子，直接返回它的金额

        // 初始化前两个位置的dp值
        dp[0] = nums[0];  // 第一个房子的最大抢劫金额就是nums[0]
        dp[1] = max(nums[0], nums[1]);  // 第二个房子的最大抢劫金额是nums[0]和nums[1]中的较大值

        // 动态规划状态转移：从第3个房子开始计算
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);  // 选择是否抢劫第i个房子
        }

        // 返回最大抢劫金额，即最后一个房子对应的dp值
        return dp[n - 1];
    }
};

其实我们只需要记录 dp[i-1] 和 dp[i-2]，而不需要完整的 dp 数组。我们可以将 dp[i-1] 和 dp[i-2] 分别存储在两个变量中，从而不再需要 dp 数组：
具体实现代码（详解版）：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        
        if (n == 0) return 0;  
        if (n == 1) return nums[0]; 
        
        // 初始化：first代表dp[i-2]，second代表dp[i-1]
        int first = nums[0];  // dp[0]，即第一个房子可以抢到的金额
        int second = max(nums[0], nums[1]);  // dp[1]，即第二个房子可以抢到的最大金额

        // 从第3个房子开始，更新状态
        for (int i = 2; i < n; i++) {
            int current = max(second, first + nums[i]);  // 当前房子的最大抢劫金额
            first = second;  // 更新dp[i-2]
            second = current;  // 更新dp[i-1]
        }

        return second;  // 最终返回second，即最大抢劫金额
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

4.完全平方数

在这里插入图片描述
思路分析：动规五部曲

dp[i]:表示和为i的最少完全平方数的个数
递推公式：
- 完全平方数的特点是：如果一个数可以被表示为若干个完全平方数之和，那么它的最小完全平方数的个数应该是通过某种方式组合这些完全平方数的最小数量。
- 假设我们已经知道 dp[i - j^2]，其中 j 是一个整数，表示一个完全平方数。那么 dp[i] 就可以通过 dp[i - j^2] + 1 来更新，表示通过加上一个完全平方数 j^2 来达到总和 i。
- 那么递推公式就是：dp[i] = min(dp[i], dp[i - j^2] + 1),其中，j^2 是小于等于 i 的所有完全平方数。
初始化：dp[0] = 0;表示和为0的最小数量为0
遍历顺序：
- 外层循环遍历所有 i 从 1 到 n。
- 内层循环遍历所有可能的完全平方数 j^2（即 j 从 1 开始，直到 j^2 大于 i）。
打印dp数组：debug

具体实现代码（详解版）：

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0; // 0 需要 0 个完全平方数
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = min(dp[i], dp[i - j * j] + 1);//递推公式
            }
        }
        
        return dp[n];
    }
};

时间复杂度：O(n * sqrt(n))，其中 n 是输入的整数。每个 i 的计算需要遍历所有小于等于 i 的完全平方数，最多进行 sqrt(n) 次操作。
空间复杂度：O(n)，我们使用了一个长度为 n+1 的数组来保存状态。

5.零钱兑换

在这里插入图片描述

dp[i]:组成金额为i所需的最少硬币数；
递推公式：
- 对于每一个金额 i（从 1 到 amount），你会检查每种硬币面额 coins[j].如果硬币面额 coins[j] 小于或等于当前金额 i，则可以通过 dp[i - coins[j]] 来获得剩余金额的最小硬币数，再加上当前硬币得到新的结果。
- dp[i] = min(dp[i], dp[i - coins[j] + 1)，其中 coins[j] 为当前考虑的硬币面额。
初始化：
- dp(amount + 1,amount + 1)；这里初始化为amount + 1很重要，amount + 1是因为最多也就是amount个1相加，再多就不可能了使用INT_MAX也可以做到，但是一旦遇到 dp[i - coin] + 1 就会导致int范围溢出，需要额外判断，或者使用其他类型比如long long，或者也可以取数据范围外的特殊值，但都取特殊值的了话还不如用这个amount + 1
- dp[0]=0;表示组成金额为0不需要任何硬币；
遍历顺序：
- 外层循环遍历所有金额 i 从 1 到 amount；
- 内存循环遍历每个硬币，对每个金额i，我们都要检查每种硬币是否能参与组成该金额（即coins[j] <= i),进而更新dp[i].
打印dp数组：debug

具体实现代码（详解版）：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1,amount + 1);

        dp[0] = 0;

        for(int i = 1 ; i <= amount ; i ++){
            for(int j = 0 ; j < coins.size() ; j ++){
                if(coins[j] <= i){//硬币面额不超过当前金额
                    dp[i] = min(dp[i],dp[i - coins[j]] + 1);
                }
            }
        }
        //因为初始化为amount + 1，若没更新就是没找到组合方式，判断即可。
        return  dp[amount] > amount ? -1 : dp[amount];
    }
};

时间复杂度：O(amount *m),其中其中 amount 是目标金额，m 是硬币的种类数。外层循环遍历金额 1 到 amount，内层循环遍历所有硬币，导致总的时间复杂度为 O(amount * m)。
空间复杂度：O(amount)，我们使用一个长度为 amount + 1 的 dp 数组来保存每个金额所需的最少硬币数。

原文地址：https://blog.csdn.net/qq_43060884/article/details/143659273

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：vector和docker的区别？
下一篇：LeetCode 第 423 场周赛个人题解

Python高级编程模式和设计模式
【代码】Python高级编程模式和设计模式。
阅读更多2024-11-15
【代码随想录】刷题记录(29)-用栈实现队列
思路其实很简单，有点像那种小学益智游戏，比如那种给两个箱子，花几步把最下面的砖块搬出来的游戏。这道题其实就是类似这种动作，因为栈是遵循“先入后出”的原则，所以如果要拿出最先入栈stack_in的元素（
阅读更多2024-11-15
Jdbc学习笔记（四）--PreparedStatement对象、sql攻击（安全问题）
在需要用户输入的地方，用户输入的是SQL语句的片段，最终用户输入的SQL片段与我们DAO中写的SQL语句合成一个完整的SQL语句！例如用户在登录时输入的用户名和密码都是为SQL语句的片段！所以，建议大
阅读更多2024-11-15
Redis简介、数据结构、高性能读写、持久化机制、分布式架构
Redis简介、数据结构、高性能读写、持久化机制、分布式架构
阅读更多2024-11-15
扩散模型生成 360度场景
扩散模型生成 360度场景
阅读更多2024-11-15
css文字间距撑满横向距离
【代码】css文字间距撑满横向距离。
阅读更多2024-11-15
Python常用魔术方法（学习笔记）
Python中常用魔术方法的使用。
阅读更多2024-11-15
如何在 Ubuntu 上安装 RStudio IDE（R语言集成开发环境） ?
RStudio 是一个功能强大的 R 语言集成开发环境(IDE)，R 是一种主要用于统计计算和数据分析的编程语言。任何从事数据科学项目或任何其他涉及 R 的类似任务的人，RStudio 都可以使您的工
阅读更多2024-11-15
开源对象存储新选择：在Docker上部署MinIO并实现远程管理
开源对象存储新选择：在Docker上部署MinIO并实现远程管理
阅读更多2024-11-15
Hot100 42接雨水
根据题目描述，雨水总和就是蓝色方块加起来的总和。怎么思路很简单，为了不让水溢出，那么两边只能取最短的一截。根据当前柱子所处的位置，算出前面最高的和后面最高的柱子（因为水是流动的），这样求最小的柱子长度
阅读更多2024-11-15

LeetCode 热题100之 动态规划1

1.爬楼梯

2.杨辉三角

3.打家劫舍

4.完全平方数

5.零钱兑换

相关文章

LeetCode 热题100之动态规划1