开发者社区> yanglbme> 正文

图文并茂!动态规划热门题目剖析

简介: Doocs 开源社区的朋友们,你们好,我是 Chunel Feng[3]。今天,我们就来简单分析几道动态规划(Dynamic Programming,简称 DP)相关的热门面试题目,陪着大家一起熟悉或复习一下这一部分知识。
+关注继续查看

Doocs 开源社区的朋友们,你们好,我是 Chunel Feng[3]。今天,我们就来简单分析几道动态规划(Dynamic Programming,简称 DP)相关的热门面试题目,陪着大家一起熟悉或复习一下这一部分知识。


开始之前,我要首先声明我的态度:刷题绝不是为了进入大厂而必经的磨难,一个人的实力如何绝不可能仅通过几道算法题目得出结论。有目的的刷题,更多的为了提升对数据结构和算法的理解,扩宽编程的思路和方法。 这些经典的思路即便暂时无法受用在你的日常工作中,也可能在某个不经意的瞬间,在你的生活中熠熠生辉。


接下来我选的 4 道题目,分别代表 4 种类型:


•斐波那契数列

•一维相邻动态规划

•二维相邻动态规划

•间隔动态规划


需要指出,有些题目我并没有给出最优解(我也会在题目后稍加说明),而是给出个人认为最容易理解、也最能契合特定 dp 类型的解法。个人水平有限,如果大家看出有什么不足,或者有更好的思路,希望随时交流指正。


一、爬楼梯


1. 题目链接:爬楼梯[4]


假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。示例 1:输入: 2输出: 2解释: 有两种方法可以爬到楼顶。1.  1 阶 + 1 阶2.  2 阶


30.png


2. 解题思路


这是一个很典型的斐波那契数列问题,也是一个很适合dp入门的题目。爬到3楼,只有两种可能:先爬到1楼,然后再一步上两层;或者先爬到2楼,然后再一步上一层。故:爬到3楼的方法数,等于爬到【1楼】的方法数和爬到【2楼】的方法数之和。爬到4楼的方法数,等于爬到【2楼】的方法数和爬到【3楼】的方法数之和。从而很容易推到出: dp[i] = dp[i-1] + dp[i-2]


3. 代码实现


class Solution {public:    int climbStairs(int n) {        // 不考虑n小于2的临界值情况了        vector<int> dp(n+1);        dp[0] = 0;        dp[1] = 1;        dp[2] = 2;        for (int i = 3; i <= n; i++) {            dp[i] = dp[i - 1] + dp[i - 2];        }        return dp[n];    }};


二、连续子数组的最大和


1. 题目链接:连续子数组的最大和[5]


给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例 1:输入:nums = [-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。


31.png


2. 解题思路


这一题更准确的说,应该是一个贪心的题目。在这里,用一维dp的方法来实现。也是在一定程度上,说明一维dp和贪心之间,有一定的关联关系。解题思路,主要就是设定一个一维dp数组,数组的每一位记录当前最大的子序列值。体现在图中,就是dp[3] = max(4, -2+4) = 4;dp[6] = max(5, 1+5) = 6;dp[i] = std::max(dp[i-1] + nums[i], nums[i]);如果有超过之前最大值的,则更新result值。


3. 代码实现


class Solution {public:    int maxSubArray(vector<int>& nums) {        vector<int> dp(nums.size());        dp[0] = nums[0];        int result = dp[0];        for (int i = 1; i < nums.size(); i++) {            dp[i] = std::max(dp[i-1] + nums[i], nums[i]);            result = std::max(dp[i], result);        }        return result;    }};


4. 补充说明


以上给出的解法,更偏向贪心和动态规划的结合。还有一种dp方法,是在dp数组中的每个值,均记录当前为止最大的子序列和是多少,然后返回dp[len-1]即可。


三、礼物的最大价值


1. 题目链接:礼物的最大价值[6]


在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?示例 1:输入:[  [1,3,1],  [1,5,1],  [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物


32.png


2. 解题思路


这是一道典型的二维动态规划的题目。dp[i][j]值表示的表示的就是,走到当前位置,最多可以拿到的礼物价值之和。在计算dp[i][j]的过程中,该值总是与grid[i-1][j-1]、dp[i-1][j]、dp[i][j-1]相关。dp[2][2] = max(dp[1][2], dp[2][1]) + grid[1][1];dp[2][3] = max(dp[1][3], dp[2][2]) + grid[1][2];dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];体现在图中,就是 9 = max(4+5, 2+5)。依次计算下去,dp矩阵右下角的值(12),即为所求。而红色的箭头,表示的就是前进的方向。


3. 代码实现


class Solution {public:    int maxValue(vector<vector<int>>& grid) {        int h = grid.size();    // 行数        int w = grid[0].size();    // 列数        if (h == 0 || w == 0) {            return 0;        }        // 生成一个二维的dp数组        vector<vector<int>> dp(h+1, vector<int>(w+1, 0));        for (int i = 0; i < h+1; i++) {            for (int j = 0; j < w+1; j++) {                if (i != 0 && j != 0) {                    // 第0行和第0列值均为0,不参与计算。                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];                }            }        }        return dp[h][w];    }};


4. 补充说明


需要说明的是,这种解法相对比较容易理解,但在空间复杂度上有一定的优化空间。当计算dp[i][j]的值的时候,其实仅用到了i行和i-1行的数据。故计算的时候,可以仅保留上一行数据,甚至是上一行中涉及到的个别数据。具体方法,大家可以自己百度一下,当做一个知识点扩展了吧。


5. 相似推荐


类似的问题,给大家推荐 leetcode中【72.编辑距离】。需要说明的一点是,编辑距离的计算过程中,还有一些可以减少时间复杂度的彩蛋哦,大家自己去发掘哈。


四、零钱兑换


1. 题目链接:零钱兑换[7]


给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。你可以认为每种硬币的数量是无限的。示例 1:输入:coins = [1, 2, 5], amount = 11输出:3解释:11 = 5 + 5 + 1


33.png


2. 解题思路


找零问题,也是属于比较经典的一种 dp 问题。相比于上面几道题目,这一题的不同点在于,这里的 dp[i] 并不是与自己相邻的 dp[i-1] 产生关系。需要根据零钱的面额,向前找k个值(体现在 dp[i] = dp[i-coins[j]] + 1 这一句代码里)。


3. 代码实现


class Solution {public:    int coinChange(vector<int>& coins, int amount) {        vector<int> dp(amount+1, -1);    // 所有数据,默认用-1占位,表示没有被计算过        dp[0] = 0;        for (int i = 1; i <= amount; i++) {            for (int j = 0; j < coins.size(); j++) {                /* 如果当前面值小于i,并且i-coins[j]面额的钱也可以被拼出。                   比如dp[7]和2块钱面额,并且 dp[7-2] != -1 */                if (coins[j] <= i && dp[i-coins[j]] != -1) {                    /* 内部循环,如果dp[i]未被计算过,或者出现更低的值,则更新dp[i]的值 */                    if (dp[i] == -1 || dp[i] > dp[i-coins[j]] + 1) {                        dp[i] = dp[i-coins[j]] + 1;                    }                }            }        }        return dp[amount];    }};


4. 补充说明


上面是的解法,如果提前将coins中的值进行排序,还可以进行一些剪枝逻辑。比如,当一旦发现 coins[j]>i,则结束内部的循环。这个主要是为了说明,动态规划中合理的加入剪枝方法,可以一定程度的降低计算的时间复杂度。


5. 相似推荐


类似的问题,给大家推荐:背包问题。背包问题,更像是找零问题的二维版本,加入了重量和价值两个影响因素。具体问题就不给大家罗列了,自行百度一下或者去B站上搜,会有很多。记得要看哦。


结束语


由于工作性质的关系,我时而会需要去实现或优化一些相对复杂的算法和数据结构。每每这个时候,之前刷 Leetcode 的一些经验和心得,就会让我觉得受益匪浅。所以,即便没有换工作的诉求,我也会偶尔抽一点时间尝试去写几道题目。现在比较流行的一些深度学习算法,本质上也就是通过动态调整参数的方式去求最优解的过程。


动态规划应该属于 Leetcode 中相对比较难的题目了,没有做过的小白,无从下手是很正常的。从上面几道题目可以看出,dp 相关的题目代码量一般都不大,如果能抽象出其中关系,保持清晰思路,coding 起来并不难。不过,写了几道题并不代表就学通了 dp 的精髓,出现“今天刷了明天忘”的情况也都是很正常的。学着感受动态规划的思路,学着把一个复杂的问题拆解成一些简单且有关联问题的,然后逐个击破并获取最优解,这才是重点。


其实,不仅在刷题中,在日常的工作中,在面对生活中的各种复杂事情时,我们更应该有这种化繁为简、并且一步一个脚印的去做的思路才对啊。


引用链接


[1] 一面之猿网: http://www.chunel.cn

[2] Caiss 智能搜索引擎: https://github.com/ChunelFeng/caiss

[3] Chunel Feng: https://github.com/ChunelFeng

[4] 爬楼梯: https://leetcode-cn.com/problems/climbing-stairs/

[5] 连续子数组的最大和: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

[6] 礼物的最大价值: https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/

[7] 零钱兑换: https://leetcode-cn.com/problems/coin-change/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19985 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
29364 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22618 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
16609 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20823 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14909 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23607 0
+关注
73
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载