浦项建设(中国)有限公司网站,南京网站建设公司哪家好,太原企业模板建站,上海建设银行网站上班时间本文由 简悦 SimpRead 转码#xff0c; 原文地址 juejin.cn 前言
我们刷 leetcode 的时候#xff0c;经常会遇到动态规划类型题目。动态规划问题非常非常经典#xff0c;也很有技巧性#xff0c;一般大厂都非常喜欢问。今天跟大家一起来学习动态规划的套路#xff0c;文章… 本文由 简悦 SimpRead 转码 原文地址 juejin.cn 前言
我们刷 leetcode 的时候经常会遇到动态规划类型题目。动态规划问题非常非常经典也很有技巧性一般大厂都非常喜欢问。今天跟大家一起来学习动态规划的套路文章如果有不正确的地方欢迎大家指出哈感谢感谢~
什么是动态规划动态规划的核心思想一个例子走进动态规划动态规划的解题套路leetcode 案例分析 公众号捡田螺的小男孩
什么是动态规划
动态规划英语Dynamic programming简称 DP是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems. 以上定义来自维基百科看定义感觉还是有点抽象。简单来说动态规划其实就是给定一个问题我们把它拆成一个个子问题直到子问题可以直接解决。然后呢把子问题答案保存起来以减少重复计算。再根据子问题答案反推得出原问题解的一种方法。 一般这些子问题很相似可以通过函数关系式递推出来。然后呢动态规划就致力于解决每个子问题一次减少重复计算, 比如斐波那契数列就可以看做入门级的经典动态规划问题。 动态规划核心思想
动态规划最核心的思想就在于拆分子问题记住过往减少重复计算。
我们来看下网上比较流行的一个例子 A “11111111 ”A “上面等式的值是多少”B 计算 “8”A : 在上面等式的左边写上 “1” 呢A : “此时等式的值为多少”B : 很快得出答案 “9”A : “你怎么这么快就知道答案了”A : “只要在 8 的基础上加 1 就行了”A : “所以你不用重新计算因为你记住了第一个等式的值为 8! 动态规划算法也可以说是’记住求过的解来节省时间’” 一个例子带你走进动态规划 – 青蛙跳阶问题
暴力递归 leetcode 原题一只青蛙一次可以跳上 1 级台阶也可以跳上 2 级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。 有些小伙伴第一次见这个题的时候可能会有点蒙圈不知道怎么解决。其实可以试想 要想跳到第 10 级台阶要么是先跳到第 9 级然后再跳 1 级台阶上去; 要么是先跳到第 8 级然后一次迈 2 级台阶上去。同理要想跳到第 9 级台阶要么是先跳到第 8 级然后再跳 1 级台阶上去; 要么是先跳到第 7 级然后一次迈 2 级台阶上去。要想跳到第 8 级台阶要么是先跳到第 7 级然后再跳 1 级台阶上去; 要么是先跳到第 6 级然后一次迈 2 级台阶上去。 假设跳到第 n 级台阶的跳数我们定义为 f(n)很显然就可以得出以下公式
f10 f9f(8)
f (9) f(8) f(7)
f (8) f(7) f(6)
...
f(3) f(2) f(1)即通用公式为: f(n) f(n-1) f(n-2)那 f(2) 或者 f(1) 等于多少呢
当只有 2 级台阶时有两种跳法第一种是直接跳两级第二种是先跳一级然后再跳一级。即 f(2) 2;当只有 1 级台阶时只有一种跳法即 f1 1
因此可以用递归去解决这个问题
class Solution {public int numWays(int n) {if(n 1){return 1;}if(n 2){return 2;}return numWays(n-1) numWays(n-2);}
}去 leetcode 提交一下发现有问题超出时间限制了 为什么超时了呢递归耗时在哪里呢先画出递归树看看 要计算原问题 f(10)就需要先计算出子问题 f(9) 和 f(8)然后要计算 f(9)又要先算出子问题 f(8) 和 f(7)以此类推。一直到 f(2) 和 f(1递归树才终止。
我们先来看看这个递归的时间复杂度吧
递归时间复杂度 解决一个子问题时间*子问题个数一个子问题时间 fn-1fn-2也就是一个加法的操作所以复杂度是 O(1)问题个数 递归树节点的总数递归树的总节点 2^n-1所以是复杂度 O(2^n)。
因此青蛙跳阶递归解法的时间复杂度 O(1) * O(2^n) O(2^n)就是指数级别的爆炸增长的如果 n 比较大的话超时很正常的了。
回过头来你仔细观察这颗递归树你会发现存在大量重复计算比如 f8被计算了两次f7被重复计算了 3 次… 所以这个递归算法低效的原因就是存在大量的重复计算
既然存在大量重复计算那么我们可以先把计算好的答案存下来即造一个备忘录等到下次需要的话先去备忘录查一下如果有就直接取就好了备忘录没有才开始计算那就可以省去重新重复计算的耗时啦这就是带备忘录的解法。
带备忘录的递归解法自顶向下
一般使用一个数组或者一个哈希 map 充当这个备忘录。
第一步f10 f(9) f(8)f(9) 和 f8都需要计算出来然后再加到备忘录中如下 第二步 f(9) f8 f7f8 f7 f(6), 因为 f(8) 已经在备忘录中啦所以可以省掉f(7),f6都需要计算出来加到备忘录中~ 第三步 f(8) f7 f(6), 发现 f(8)f(7),f6全部都在备忘录上了所以都可以剪掉。 所以呢用了备忘录递归算法递归树变成光秃秃的树干咯如下 带备忘录的递归算法子问题个数 树节点数 n解决一个子问题还是 O(1), 所以带备忘录的递归算法的时间复杂度是 O(n)。接下来呢我们用带备忘录的递归算法去撸代码解决这个青蛙跳阶问题的超时问题咯~代码如下
public class Solution {//使用哈希map充当备忘录的作用MapInteger, Integer tempMap new HashMap();public int numWays(int n) {// n 0 也算1种if (n 0) {return 1;}if (n 2) {return n;}//先判断有没计算过即看看备忘录有没有if (tempMap.containsKey(n)) {//备忘录有即计算过直接返回return tempMap.get(n);} else {// 备忘录没有即没有计算过执行递归计算,并且把结果保存到备忘录map中对1000000007取余这个是leetcode题目规定的tempMap.put(n, (numWays(n - 1) numWays(n - 2)) % 1000000007);return tempMap.get(n);}}
}去 leetcode 提交一下如图稳了 其实还可以用动态规划解决这道题。
自底向上的动态规划
动态规划跟带备忘录的递归解法基本思想是一致的都是减少重复计算时间复杂度也都是差不多。但是呢
带备忘录的递归是从 f(10) 往 f(1方向延伸求解的所以也称为自顶向下的解法。动态规划从较小问题的解由交叠性质逐步决策出较大问题的解它是从 f(1) 往 f(10方向往上推求解所以称为自底向上的解法。
动态规划有几个典型特征最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中
f(n-1) 和 f(n-2) 称为 f(n) 的最优子结构f(n) fn-1fn-2就称为状态转移方程f(1) 1, f(2) 2 就是边界啦比如 f(10) f(9)f(8),f(9) f(8) f(7) ,f(8) 就是重叠子问题。
我们来看下自底向上的解法从 f(1) 往 f(10方向想想是不是直接一个 for 循环就可以解决啦如下 带备忘录的递归解法空间复杂度是 O(n)但是呢仔细观察上图可以发现fn只依赖前面两个数所以只需要两个变量 a 和 b 来存储就可以满足需求了因此空间复杂度是 O(1) 就可以啦 动态规划实现代码如下
public class Solution {public int numWays(int n) {if (n 1) {return 1;}if (n 2) {return 2;}int a 1;int b 2;int temp 0;for (int i 3; i n; i) {temp (a b)% 1000000007;a b;b temp;}return temp;}}动态规划的解题套路
什么样的问题可以考虑使用动态规划解决呢 如果一个问题可以把所有可能的答案穷举出来并且穷举出来后发现存在重叠子问题就可以考虑使用动态规划。 比如一些求最值的场景如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等都是动态规划的经典应用场景。
动态规划的解题思路
动态规划的核心思想就是拆分子问题记住过往减少重复计算。 并且动态规划一般都是自底向上的因此到这里基于青蛙跳阶问题我总结了一下我做动态规划的思路
穷举分析确定边界找出规律确定最优子结构写出状态转移方程
1. 穷举分析
当台阶数是 1 的时候有一种跳法f1 1当只有 2 级台阶时有两种跳法第一种是直接跳两级第二种是先跳一级然后再跳一级。即 f(2) 2;当台阶是 3 级时想跳到第 3 级台阶要么是先跳到第 2 级然后再跳 1 级台阶上去要么是先跳到第 1 级然后一次迈 2 级台阶上去。所以 f(3) f(2) f(1) 3当台阶是 4 级时想跳到第 3 级台阶要么是先跳到第 3 级然后再跳 1 级台阶上去要么是先跳到第 2 级然后一次迈 2 级台阶上去。所以 f(4) f(3) f(2) 5当台阶是 5 级时… 2. 确定边界
通过穷举分析我们发现当台阶数是 1 的时候或者 2 的时候可以明确知道青蛙跳法。f1 1f(2) 2当台阶 n3 时已经呈现出规律 f(3) f(2) f(1) 3因此 f1 1f(2) 2 就是青蛙跳阶的边界。
3. 找规律确定最优子结构
n3 时已经呈现出规律 f(n) f(n-1) f(n-2) 因此f(n-1) 和 f(n-2) 称为 f(n) 的最优子结构。什么是最优子结构有这么一个解释 一道动态规划问题其实就是一个递推问题。假设当前决策结果是 f(n), 则最优子结构就是要让 f(n-k) 最优, 最优子结构性质就是能让转移到 n 的状态是最优的, 并且与后面的决策没有关系, 即让后面的决策安心地使用前面的局部最优解的一种性质 4 写出状态转移方程
通过前面 3 步穷举分析确定边界最优子结构我们就可以得出状态转移方程啦 5. 代码实现
我们实现代码的时候一般注意从底往上遍历哈然后关注下边界情况空间复杂度也就差不多啦。动态规划有个框架的大家实现的时候可以考虑适当参考一下
dp[0][0][...] 边界值
for(状态1 所有状态1的值){for(状态2 所有状态2的值){for(...){//状态转移方程dp[状态1][状态2][...] 求最值}}
}leetcode 案例分析
我们一起来分析一道经典 leetcode 题目吧 给你一个整数数组 nums 找到其中最长严格递增子序列的长度。 示例 1
输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2
输入nums [0,1,0,3,2,3]
输出4我们按照以上动态规划的解题思路
穷举分析确定边界找规律确定最优子结构状态转移方程
1. 穷举分析
因为动态规划核心思想包括拆分子问题记住过往减少重复计算。 所以我们在思考原问题数组 num[i] 的最长递增子序列长度时可以思考下相关子问题比如原问题是否跟子问题 num[i-1] 的最长递增子序列长度有关呢
自顶向上的穷举
这里观察规律显然是有关系的我们还是遵循动态规划自底向上的原则基于示例 1 的数据从数组只有一个元素开始分析。
当 nums 只有一个元素 10 时最长递增子序列是 [10], 长度是 1.当 nums 需要加入一个元素 9 时最长递增子序列是 [10] 或者[9], 长度是 1。当 nums 再加入一个元素 2 时最长递增子序列是 [10] 或者 [9] 或者[2], 长度是 1。当 nums 再加入一个元素 5 时最长递增子序列是 [2,5], 长度是 2。当 nums 再加入一个元素 3 时最长递增子序列是 [2,5] 或者[2,3], 长度是 2。当 nums 再加入一个元素 7 时, 最长递增子序列是 [2,5,7] 或者[2,3,7], 长度是 3。当 nums 再加入一个元素 101 时最长递增子序列是 [2,5,7,101] 或者[2,3,7,101], 长度是 4。当 nums 再加入一个元素 18 时最长递增子序列是 [2,5,7,101] 或者 [2,3,7,101] 或者 [2,5,7,18] 或者[2,3,7,18], 长度是 4。当 nums 再加入一个元素 7 时, 最长递增子序列是 [2,5,7,101] 或者 [2,3,7,101] 或者 [2,5,7,18] 或者[2,3,7,18], 长度是 4.
分析找规律拆分子问题
通过上面分析我们可以发现一个规律
如果新加入一个元素 nums[i], 最长递增子序列要么是以 nums[i] 结尾的递增子序列要么就是 nums[i-1] 的最长递增子序列。看到这个是不是很开心nums[i] 的最长递增子序列已经跟子问题 nums[i-1] 的最长递增子序列有关联了。
原问题数组nums[i]的最长递增子序列 子问题数组nums[i-1]的最长递增子序列/nums[i]结尾的最长递增子序列是不是感觉成功了一半呢但是如何把 nums[i] 结尾的递增子序列也转化为对应的子问题呢要是 nums[i] 结尾的递增子序列也跟 nums[i-1] 的最长递增子序列有关就好了。又或者 nums[i] 结尾的最长递增子序列跟前面子问题 num[j]0ji结尾的最长递增子序列有关就好了带着这个想法我们又回头看看穷举的过程 nums[i] 的最长递增子序列不就是从以数组 num[i] 每个元素结尾的最长子序列集合取元素最多也就是长度最长那个嘛所以原问题我们转化成求出以数组 nums 每个元素结尾的最长子序列集合再取最大值嘛。哈哈想到这我们就可以用 dp[i] 表示以 num[i] 这个数结尾的最长递增子序列的长度啦然后再来看看其中的规律 其实nums[i] 结尾的自增子序列只要找到比 nums[i] 小的子序列加上 nums[i] 就可以啦。显然可能形成多种新的子序列我们选最长那个就是 dp[i] 的值啦 nums[3]5, 以5结尾的最长子序列就是[2,5], 因为从数组下标0到3遍历只找到了子序列[2]比5小所以就是[2][5]啦即dp[4]2nums[4]3, 以3结尾的最长子序列就是[2,3], 因为从数组下标0到4遍历只找到了子序列[2]比3小所以就是[2][3]啦即dp[4]2nums[5]7以7结尾的最长子序列就是[2,5,7]和[2,3,7], 因为从数组下标0到5遍历找到2,5和3都比 7 小所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]这些子序列最长子序列就是[2,5,7]和[2,3,7]它俩不就是以5结尾和3结尾的最长递增子序列 [7] 来的嘛所以dp[5]3 dp[3]1dp[4]1。 很显然有这个规律一个以 nums[i] 结尾的数组 nums
如果存在 j 属于区间 [0i-1], 并且 num[i]num[j] 的话则有dp(i) max(dp(j))1
最简单的边界情况
当 nums 数组只有一个元素时最长递增子序列的长度 dp(1)1, 当 nums 数组有两个元素时dp(2) 2 或者 1 因此边界就是 dp(1)1。
确定最优子结构
从穷举分析我们可以得出以下的最优结构
dp(i) max(dp(j))1存在j属于区间[0i-1],并且num[i]num[j]。max(dp(j)) 就是最优子结构。
状态转移方程
通过前面分析我们就可以得出状态转移方程啦 所以数组 num[i] 的最长递增子序列就是
最长递增子序列 max(dp[i])代码实现
class Solution {public int lengthOfLIS(int[] nums) {if (nums.length 0) {return 0;}int[] dp new int[nums.length];//初始化就是边界情况dp[0] 1;int maxans 1;//自底向上遍历for (int i 1; i nums.length; i) {dp[i] 1;//从下标0到i遍历for (int j 0; j i; j) {//找到前面比nums[i]小的数nums[j],即有dp[i] dp[j]1if (nums[j] nums[i]) {//因为会有多个小于nums[i]的数也就是会存在多种组合了嘛我们就取最大放到dp[i]dp[i] Math.max(dp[i], dp[j] 1);}}//求出dp[i]后dp最大那个就是nums的最长递增子序列啦maxans Math.max(maxans, dp[i]);}return maxans;}
}参考与感谢
leetcode 官网《labuladong 算法小抄》
