算法数据结构——这张图说尽动态规划算法
码农天地 -
算法中有个专题，动态规划，它十分的重要，大厂面试中或多或少有所涉及，来网易之前，刷了部分dp，这次正好再次梳理一遍，希望对你们有一点点帮助。
如果你已经懂了dp思路，或者已经掌握了常见的dp解法，可以直接跳过。
如果你还不了解，或者知道动态规划，但是还没有开始刷题的话，可能这篇文章适合你。
加群973961276即可获得更多脑图和视频电子书资料
联系?TianTianUp，遇到问题的话，可以联系作者噢，愿意陪你一起学习一起探讨问题。
脑图?
如果觉得看完文章有所收获的话，可以关注我一下哦
知乎：秃顶之路
b站：linux亦有归途
每天都会更新我们的公开课录播以及编程干货和大厂面经
或者直接点击链接
https://ke.qq.com/course/4177...
来课堂上跟我们讲师面对面交流
需要大厂面经跟学习大纲的小伙伴可以加群973961276获取
动态规划（Dynamic Programming），因此常用 DP 指代动态规划。动态规划，首先我们得清楚，它的概念是啥，它能解决什么问题，维基百科对它的解释?
动态规划在寻找有很多重叠子问题的情况的最佳解时有效。它将问题重新组合成子问题，为了避免多次解决这些子问题，它们的结果都逐渐被计算并被储存，从简单的问题直到整个问题都被解决。因此，动态规划储存递归时的结果，因而不会在解决同样的问题时花费时间。动态规划只能应用于有最佳子结构的问题。最佳子结构的意思是局部最佳解能决定全域最佳解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。
我稍微总结一下?
将一个大的问题拆分成一个个子问题，我们把它称之为子结构。每个最优解，也就是最优值均由[这些小规模子问题]推到而来。更重要的就是利用历史记录，来避免我们重复的计算。什么是重复计算，那怎么样可以利用历史记录来减少我们不必要的运算呢?
我们拿斐波那契数列这题来看?
如果我们按照这个递归的写法来看，那么它的过程如下?
它会多次计算结果，这个符合动态规划的点，动态规划在寻找有很多重叠子问题的情况的最佳解时有效。而且对于这个问题而言，它可以继续去拆分，变成更小的子问题去解决，它也符合动态规划的预期。
那么这里只是举个例子，后续会将做题思路?
动态规划解题三大步骤对于初学者而言，需要短时间就掌握的话，我觉得挺难的，所以这里我推荐大家可以看看经典的动态规划?背包九讲，点这里，看完它，或许对你有点帮助吧。
解题思路，三大步骤?
状态定义列出状态转移方程初始化状态*状态定义
我们需要借助数组来保存之前计算的结果，所以一般采用的就是数组来维护我们的结果，一般dp数组。dp数组的含义一定要明确，也就是说，dp[i]表达是啥意思，举个例子，dp[i]表达到达第i个阶梯时的方案数。*列出状态转移方程
通俗易懂的话，找出数组间关系式，这个时解决动态规范问题中，最难也是最重要的一步。通常情况而言，dp[i]个状态的转移方程，跟dp[i-1] 与 dp[i-2] 之间存在某种联系。举个例子，后续爬梯子的题目中，状态转移方程?
dp[i] = dp[i-1] + dp[i-2]
复制代码那么爬到第i阶梯，有两种情况?
从第i-1阶梯再爬1阶就到第i阶从第i-2阶梯再爬2阶就到第i阶那么它的状态方程转移就是上面的式子*初始化状态
我们会发现，dp数组的第n项结果，是由状态转移方程求解而言的，所以我们需要的是第n-1项，n-2项，或者n-3项的值。这个时候，我们就需要初始话dp数组的值，一般而言，比如dp[1],dp[2],dp[1][1],dp[1][2]。从上面的场景，爬楼梯来说，我们需要初始话哪一项dp数组呢，当我们依次迭代到dp[3] = dp[1] + dp[2]，接下来就不再需要去分解了。
这个时候，我们实际意义而言，就需要我们去初始化，dp[1]和dp[2]数组。
动态规划分类这么久以来，随着动态规划这种算法思路被很多牛人去探索，动态规划这类问题，被分为了很多种，参考网上的资料，列举了几个常见的dp，我们接下来看看吧。
我的经验之谈，按照不同dp专题来刷，效果很明显，当然了，具体看你自己掌握情况，以及刷题速度了。
背包dp这算是状态规划中比较经典的题目了，对于理解dp的话，我个人觉得很有帮助，也是我入门dp最开始看的专题?
dd大牛的《背包九讲》 ?，可以看看这篇，这里就不展开了。
这里推荐几道题?
分割等和子集- 01背包目标和 - 01背包-求方案数零钱兑换 - 完全背包零钱兑换- II (完全背包-求方案数)一和零 - (二维费用背包)*线性dp顾名思义，线性DP就是在一条线上进行DP。或者我的理解是，就是在线性空间上的递推。这里推荐几道题?
最长上升子序列三角形最小路径和最长公共子序列最大子序和俄罗斯套娃信封问题*区间dp顾名思义，在一段区间上dp，类似于dp[l][r]构成的，我们也是将大问题拆分成小问题来处理，这里就是拆分成小区间来处理。然后对小区间处理后，再回溯的求出大区间的值。主要的方法有两种，记忆化搜索和递推。这里推荐几道题?
最长回文子序列统计不同回文子序列多边形三角剖分的最低得分戳气球奇怪的打印机*树形dp准确的来说，树形dp准确的说是一种dp的思想，将dp建立在树状结构的基础上。你可以理解成，在一颗树上定义dp方程式，完成相应的操作。这里推荐几道题?
打家劫舍 III时态同步选课二叉树中的最大路径和二叉树的直径战略游戏*数位dp数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！这里推荐几道题?
数字 1 的个数最大为 N 的数字组合可被 K 整除的最小整数我印象中，这个是模板，自己写很难，但是这是个板子题，哈哈哈，打过Acm都知道，这里就不展开了。
状态压缩DP计数型DP递推型DP概率型DP博弈型DP，嗯太多了，只当是抛砖引玉吧。
3个例子接下来，我们就以三题为例子，来强化我们解题思路的三大步骤吧?
爬楼梯⭐链接：爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶复制代码
```
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶复制代码
```
我们按照解题思路走一遍?
第一步：状态定义
dp[i] 表示的含义:到第i阶方案数
第二步： 确定状态转移方程
根据实际的情况，我们很容易想到?
到第i阶梯有两种方式第一种, 从i-1向上走一步即可第二中，从i-2向上走二步即可所以 dp[i] = dp[i-1] + dp[i-2]第三步,初始化状态，dp数组
dp[1] = 1,dp[2] = 2
复制代码按照这个三步走的话，我们就可以写出完整的解题代码
代码?
代码点这里☑️
打家劫?⭐⭐链接：打家劫舍 II你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
复制代码示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
复制代码我们按照解题思路走一遍?
第一步：状态定义
// 这里就利用二维状态,既然可以选择偷或者是不偷
// dp[i][0] 表示不偷当前第i个房间,获取最高金币数
// dp[i][1] 表示的是偷第i房间,获取最高金币数
复制代码第二步： 确定状态转移方程
// 第i个房间偷的话,dp[i][1] = nums[i] + dp[i-1][0]
// 第i个房间不偷的话, dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])
复制代码第三步,初始化状态，dp数组
// dp[0][0] = 0
// dp[0][1] = nums[0]
复制代码但是这个题目的难点在于?
第一个房子跟最后一个房子是挨着的，意味着我们需要做些改变，这个我也是在提示下完成的，写法很巧妙，我们具体看下代码下?
按照这个三步走的话，我们就可以写出完整的解题代码?
代码点这里☑️
买卖股票的最佳时机 IV⭐⭐⭐给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
链接：买卖股票的最佳时机 IV给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
复制代码示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
复制代码来源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
第一步：状态定义
// 可以定义如下
// dp[i][j][0] 表示第i天交易了j次时卖出后的累计最大利润
// dp[i][j][1] 表示第i天交易了j次时买入后的累计最大利润
复制代码第二步： 确定状态转移方程
// 第二步：确定状态转移方程
// dp[i][j][0] 当第i天不持股的话，我们需要确定昨天是否持有股票
// dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
// dp[i][j][1] 同样的第i天,我们需要去确定昨天是否持有股票
// dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
复制代码第三步,初始化状态，dp数组
// 所有不持股的状态值初始化的时候为 0。所有持股的状态值都设置为一个很大的负数（至少应该是最大的股价的负数 - 1），表示未知。
// dp[0][j][0] = 0;
// dp[0][j][1] = -prices[i];
复制代码但是这个题目的难点在于?
当k大于len/2的时候，我们需要做一个处理，或者说，我们需要利用状态压缩，好难，我们看看该如何写吧?
进阶题目汇总以下是我收集的部分题目，希望对你们有帮助。
简单爬楼梯打家劫舍使用最小花费爬楼梯连续数列三步问题*中等打家劫舍 II最佳买卖股票时机含冷冻期打家劫舍 III不同路径不同路径 II最长上升子序列*困难买卖股票的最佳时机 III买卖股票的最佳时机 IV青蛙过河单词拆分 II最大子矩阵感谢大家看到这里，如果意犹未尽的话可以看看我的其他文章哦
1、一张脑图带你彻底掌握Git
2、学会这些linux知识之后，我承认我有点飘了
3、linux socket编程，不限于linux，一切皆socket
Tags 标签
加个好友，技术交流
