本篇其实是去年的时候在部门内部做的一次简单的分享的内容，也是对自己坚持学习了一个多月的动态规划内容的一些简单的总结和整理
从斐波那契数列到01背包问题
起始
在正式介绍动态规划之前，我们先从一个简单且不陌生的题目开始
斐波那契数列
首先我们来看下这个题目
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1这里我们题面已经明确的给出了实现的逻辑了，是的，就是一眼就能看出来的递归。
最基本的实现代码如下，非常的简单，也很好理解
class Solution {
public int fib(int n) {
if (n<2){
return n;
}
return fib(n-1) + fib(n-2);
}
}但是，真的就这样结束了么？显然不是，首先我们能直观的看到这个是一个递归的过程，如果输入的n不是很大尚且还好，但是当你的n足够大的时候，比如20000?虽然这也不是非常大，那么会发生什么呢？
此时也许你会说，那我可以改jvm参数，增大可用栈深度，那你的栈深度又能增加到多少呢？200万？还是2000万？ 我们不妨仔细分析一下这个过程
F( n ) = F(n - 1) + F(n - 2)
F( n - 1 ) = F(n - 2) + F(n - 3)
F( n - 2 ) = F(n - 5) + F(n - 4)
F( n - 3 ) = F(n - 4) + F(n - 5)可以很容易的看出来，中间经历的大量的重复运算，思考一下，我们是不是有什么办法能把这个中间的大量的重复运算的过程省略过去呢？
这个时候你也许会想到哈希表，是的，这个方向是对的，不过在面对这种int的key的时候，我们一般有一种更加简单更加轻便的作法来实现哈希表的功能，那就是数组。我们可以声明一个int[]的数组来实现我们需要的功能，且其本身比Map型数据结构更加的轻便简单，相对的速度也更快
而且，这个过程中，我们不再是从F(N)向F(0)求解，而是正向的从0向N求解，那么代码如下
class Solution {
public int fib(int n) {
if (n<2){
return n;
}
int[] dp = new int[n+1];
dp[1] = 1;
int idx = 1;
while (++idx <=n){
dp[idx] = dp[idx-1] + dp[idx-2];
}
return dp[n];
}
}我们在算法中，给这样这种的数组一个独特的名字叫滚动数组，这样是不是就规避了最大栈深度的限制了呢？那我们入参给个Integer.MAX_VALUE看看会发生什么？内部的值相加是否会超出int型上限我们姑且先不论，直接入参给入跑一下看看
那么接下来我们要对这份代码再做一点优化，而数组长度上限的问题，你可以自己再思考下看看这个问题"java中数组的长度上限是多少"而又为什么会有这个上限。
拓展小知识：循环遍历和递归是可以相互转化的，最经典的例子莫过于二叉树的深度优先搜索(DFS)和广度优先搜索(BFS)，一个是递归遍历，一个是循环遍历，这是另外一个不小的话题，这里不做展开讨论了现在我们再次观察下这份代码，n位置的值，只和n-1和n-2位置的值有关，那么我们就确实没有必要声明一个长度为n+1的数组，对此我们做一点点修改
class Solution {
public int fib(int n) {
if (n<2){
return n;
}
int[] dp = {0,1};
int idx = 1;
while (++idx <= n){
dp[idx%2] = dp[0] + dp[1];
}
return dp[(--idx)%2];
}
}当然你也完全可以声明两个变量来保存n-1和n-2的值，然后把n的值更新到n-2的变量上。
理解了上面这些操作之后，我们就算是对动态规划问题有一点点基础的了解了，接下来让我们来看下动态规划的基本定义。
入门第一步
基本概念
动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划不是某一种具体的算法，而是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
应用这种算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题之间的关系这两方面有一些要求，它们分别对应了最优子结构和重复子问题。
在之前的斐波那契的例子中，就对这个基本概念做了非常准确的说明，想要求F(n)，那就把他分解为F(n-1)和F(n-2)两个子问题来处理，处理了这两个子问题那么F(n)的问题也就迎刃而解了
另外注意一下，动态规划和分治的区别。
解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。
这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。
转移方程
另外动态规划问题中的一个最重要的东西转移方程，他表示了动规问题中，阶段与阶段之间的转化方式，还是前面讲到的斐波那契的问题，他的转移方程就是
F(n) = F(n - 1) + F(n - 2)从难度上来说，动态规划问题并不算是难度非常高的题目，一个动态规划问题，一旦你能写出他的转移方程了，那么剩下就是非常简单的编码工作了。而动态规划问题难就难在如何去发现总结归纳出他的转移方程，你的滚动数组上的值代表的含义又能否正确的帮助你解决这个问题，这个过程可能需要大量的练习才能实现，当你一拿到某个动态规划问题的时候，需要凭借自身的经验归纳总结出他的转移方程
好的，在对动态规划的概念有了基本的认知之后让我们来找个题目来初试牛刀
上手第一道题
首先，看这青蛙跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。他给出了这样一个示例
输入：n = 2
输出：2我们分析一下，每次可以跳1或者2个台阶，那么可以说明当这个青蛙在第n级台阶的时候，他可以是由第n-1或者n-2的台阶过来的。
我们声明一个dp数组int[] dp，下标表示台阶，而值标示到达这级可以经过的跳法数量，可知，当第0个台阶的时候有1种方法dp[0] = 1, 而第一级台阶的时候也只有一种方法，因为青蛙只能跳一级到达这个台阶，第二级台阶的时候可以是从第0级直接跳2级过来，也可以是从第一级跳跳一下过来到达这个层级，那么第二级的数量就是2
同样的第三级可以是第二级跳一个台阶到达，也可以是第一级跳两个台阶到达，那么就是 第一级台阶的方案总和加上第二级台阶的方案总和。
至此，到了这一步我们就已经非常明确的能总结出对应的转移方程了
dp[n] = dp[n-1] + dp[n-2]是不是和斐波那契的非常像，只是初始的边界值有所不同，这里的dp[0] = 1,dp[1] = 1,至于取模的操作，也只是多一步运算罢了。
看下代码吧
class Solution {
public int numWays(int n) {
if (n<2){
return 1;
}
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
int idx = 1;
while (++idx <= n){
dp[idx] = dp[idx-1] + dp[idx-2];
if (dp[idx] >= 1000000007){
dp[idx] -= 1000000007;
}
}
return dp[n];
}
}而把dp数组转换成2个变量的写法，我这里就省去不再写一遍了，这样的基本操作相信大家自己也能非常容易写出来。
再看下爬楼梯这题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。可以看到和前面的青蛙跳台阶是一模一样的，这里我们就不再次分析讲解一遍了。
接下来，让我们开始动态规划的正式入门之旅
从经典题正式入门
这是一道历史久远且非常经典的动态规划入门级题目，他最早出现可以追溯到 1994 年的 IOI（国际信息学奥林匹克竞赛）的题目，曾经的国际竞赛的题目，现在已经变成了一道基本入门题，可见算法这个行业的飞速发展，好了回归正题，然我看下这个题目
给定一个三角形 `triangle` ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1
的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。 2
3 4
6 5 7
4 1 8 3自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
到这里可以暂停一下，3分钟思考，我们该如何解答这样的问题。
让我回忆一下刚刚我们说到的dp数组，dp数组上的值标示了到当前阶段的时候的情况。在这题中，给出的数组第n行就有n个元素。如果我们把每行的数字都靠左排列就会是这样
2
3 4
6 5 7
4 1 8 3每行的i个元素，可以由上一行的第i个元素和i-1位置的元素走过来，第就目前的例子中的这个三角形数组，我们可以建立这样的一个dp数组
int[][] dp = new int[n][n]在和原数组对应的额位置上的值，表示到达当前位置的时候的最小值，而如果要dp[row][col]的值最小，则应当取第dp[row-1][col-1]和dp[row-1][col]这两个位置中较小的一个作为过来的方向，而到达当前位置的时候还需要再加上对应的triangle[row][col]上的值
那么我们可以试着写一些对应的转移方程
dp[row][col] = min(dp[row-1][col-1], dp[row-1][col]) + triangle[row][col]
到了这里，问一下你能想出来这题应该怎么做了么嘛？当然还有一些边界性的问题，比如
- 每行第一个元素的上一行左边是没有元素的，即数组是不存在下标为-1的，这个我们可以用边界判断的方法来处理，当遇到下标为-1的时候我们就默认返回一个不合理的值，比如题目要求最小值，那么我就设置一个很大的不在范围内的比如
20002，因为题面中给出了一个值的范围-104 <= triangle[i][j] <= 104。但是这里，我们介绍另外一种方法，我们给声明的dp数组并不只是int[n][n]的，而是声明一个int[n+1][n+1]的数组，这样就能规避掉数组越界的问题 - 第二个问题，当我们到达底层的时候。我们需要再遍历一遍底层的所有值，找出最小的那个。
好了下面让我们来写一下代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n+1][n+1];
int row = 0;
while (++row <= n){
Arrays.fill(dp[row],20002);
int col = 0;
while (++col <= row){
dp[row][col] = Math.min(dp[row-1][col],dp[row-1][col-1]) + triangle.get(row-1).get(col-1);
}
}
int min = Integer.MAX_VALUE;
int idx = 0;
while (++idx <=n){
min = Math.min(min,dp[n][idx]);
}
return min;
}
}几分钟时间，看下代码理解一下
那么在理解了这份代码之后呢，我们不妨换个角度再来想一下，既然从上往下走可以，那么我们从下往上走是不是也可以呢？整个的路径都是一样的，只是方向不一样，不妨看下这份代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n+1][n+1];
for(int i = n-1; i>=0; i--){
for(int j = 0; j<=i; j++){
dp[i][j] = triangle.get(i).get(j) + Math.min( arr[i+1][j], arr[i+1][j+1] );
}
}
return dp[0][0];
}
}是不是看起来整个风格都不大一样了？是的，因为到达最顶层的时候，已经就剩下一个可选元素了，那么到这个位置的时候必然是最小的值。
这两种不同的方式格子有各自的名字，而且特别的直观好理解，分别是
自顶向下和自底向上
除了这两种处理方向上的区别，在值的处理上也是有两种区别的，分别是
我从哪里来 和 我到哪里去
我从哪里来的比较好理解，像是上面我们之前分析的几个题目都是我从哪里来类型的，也直观的比较好理解
即 dp[row][col] = min(dp[row-1][col-1], dp[row-1][col]) + triangle[row][col]这样的转移方程表示的dp[row][col]来源于dp[row-1][col-1], dp[row-1][col]这两个之中较小的那个
那么我到哪里去又是怎么个理解呢？还是这一题，我们不妨看下下面这份代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[n-1][i] = triangle.get(n-1).get(i);
}
int row = n;
while (--row > 0){
int col = -1;
while (++col<=row){
int num = dp[row][col];
if (col>0){
int upLeft = triangle.get(row-1).get(col-1);
dp[row-1][col-1] = Math.min(num + upLeft,dp[row-1][col-1]);
}
if (col<row){
int upRight = triangle.get(row-1).get(col);
dp[row-1][col] = num + upRight;
}
}
}
return dp[0][0];
}
}再稍微花几分钟时间看下这个代码，当我们在遍历dp数组的时候，比如此时我们在dp[row][col]位置，那么我们对应的尝试往dp[row-1][col]和dp[row-1][col-1]两个位置前进，当然必须加上对应位置的值，也就是取到triangle.get(row-1).get(col-1)和triangle.get(row-1).get(col)相加之后的值，并判断这个值是否小于已经算过的情况，如果小于已经算过的情况，则取较小的这个值。这就是我到哪里去的解题思路。
自顶向下、自底向上、我从哪里来 和 我到哪里去这几种情况，在不同的问题场景下各有优劣，选择合适的思路解题方式，会使让你的解题过程有很大的差别。
到了这里，然我们再次回顾下现在的内容，每一行的值，只和上一行的值是向关联的，有没有什么办法想之前斐波那契数列那样用更少的空间来处理呢？答案是肯定的有
不妨回去看下前面的几种写法，第dp[row-1][col]位的值来源于dp[row][col]和dp[row][col+1],而dp[row-1][col+1]位的值来源于dp[row][col+1]和dp[row][col+2],可以看到第dp[row][col]位在dp[row-1][col]计算过之后就再也用不到了，这样我们完全可以把二维dp[][]数组，压缩成一维的dp[]数组
看下这份代码
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = triangle.get(n-1).get(i);
}
int row = n-1;
while (--row>=0){
int col = -1;
while (++col <= row){
dp[col] = Math.min(dp[col], dp[col+1]) + triangle.get(row).get(col);
}
}
return dp[0];
}
}好了，这一题已经相应引出的动态规划的相关思路概念问题，就先到这里，我们稍微拓展一下，看一个题外话
这个题目中这样的三角形的路径的问题，我们还有一个非常相似的模板，就是著名的杨辉三角。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1相应的也有题目，杨辉三角, 杨辉三角 II ，不过概念给得很清楚，等同于转移方程就已经直接告诉你了，所以这两题基本就算你没有学过动态规划应该也能非常容易的解出来。
那么，接下来让我正式开始动态规划的探索之旅
基本问题类型
单串问题
系列1 :股票问题
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。根据题面，这里我们直接来分析下这组示例数据
当天股票价格 7, 1, 5, 3, 6, 4
截止当天最低入手价 7 1 1 1 1 1
能赚得的利润 0 0 4 4 5 5- 第一天的时候价格为7，截止当天最低入手价为7，可得利润为0
- 第二天的时候价格为1，截止当天最低入手价为1，可能利润为依旧为0
- 第三天，价格为5，截止当天最低入手价为1，那么如果当天卖掉的话可得最大利润为4
- 第四天，价格为3，最低入手价依旧为1，当天卖掉可得利润是2，但是最大利润依是前一天的4
- 第五条，借个为6，最低入手价1，可得最大利润变为了今天卖掉的情况，利润为5
- 第六条，省略了
经过了以上的分析之后，我们可以看到一个非常关键的信息，就是当天之前的最低入手价。我们可以定义一个dp[]数组，用来保存当到达某天的时候能够入手的最低价，而当天的利润则是用每天的价格减去截止当天能获取到的最低入手价，至于最大利润则是每天能获得的利润中最大的那个值，当然你也可以dp[]数组省略用一个变量来代替
其中总结出来的状态转移方程是用来定义截止到某天能获得的最低入手价
dp[i] = min( dp[i-1], price[i] );代码
class Solution {
public int maxProfit(int[] prices) {
if (prices.length==0)return 0;
int minBuyIn = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
minBuyIn = Math.min(minBuyIn,prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minBuyIn);
}
return maxProfit;
}
}买卖股票问题是动态规划问题学习过程中最常学习到的教程，他们有很多种的变种，从简单入门到困难题型都有，适合逐步的，一点点深入学习理解，下面我们来看下他的一个变种
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。题面内容和之前一样，但是其中一个条件变了，不再是只能交易一次，而是可以多次交易，这样的话问题又该如何分析呢？
我们定义分析得到这样两个状态，一个是当天的时候手上持有股票，另一个是不持有股票，
如果今天是持有股票的话，那么上一个状态有两种，1：昨天就持有了，今天仍然持有；2：昨天没有持有股票，今天新买了股票
如果是今天没有持有股票的话，那么上一个状态也有两种可能，1：昨天持有了股票，但是今天卖掉了；2：昨天没有持有股票。今天继续不持有股票
这样我们声明一个二维dp[n][2]数组，其中dp[i][0]表示今天不持有的情况，dp[i][1]表示今天持有的情况
那么我们根据前面的分析
//今天不持有
dp[i][0] = max(dp[i-1][1]+price[i] , dp[i-1][0])
//今天持有
dp[i][1] = max(dp[i-1][0]-price[i], dp[i-1][1])这样我们就有了转移方程，至于初始边界条件，第一天不持有的话利润肯定为0，如果持有的话利润为-price[0]，最后一天的话当然是不持有的情况下能获得更多利润。
至此，代码
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][1] = -prices[0];
for (int i = 1; i < dp.length; i++) {
//如果今天不持有，则可能是昨天就不持有，或者把昨天持有的卖掉了赚到了prices[i]的钱
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
//如果今天持有，可能是昨天就持有的，或者是昨天没持有今天买了 prices[i]的钱，需要减去这么多
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[dp.length-1][0];
}
}当然还有另外一个思路，只要今天的价格比昨天的高，那就抛出股票赚取利润，代码如下，这个其实的贪心算法的思路了，和动态规划还是有着本质区别的，这里不做另外展开了。
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i]>prices[i-1]){
profit += prices[i] - prices[i-1];
}
}
return profit;
}
}下面我们看下买卖股票第三题
题面信息和之前的题面一样，但是条件又改了一点点
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。你只能进行两笔交易了。可以花点时间思考下，关键在于dp数组的表意状态定义。以及如何归纳总结出对应的转移方程
这边给出用来定义的几个状态
- 不买也不卖
- 只进行一次买入
- 进行了一次卖出
- 进行了第二次买入
- 已经对应的第二次卖出
class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length][5];
//不做任何操作
// dp[0][0] = 0;
//第一次买入
dp[0][1] = -prices[0];
//第一次买出
// dp[0][2] = 0;
//第二次买入
dp[0][3] = -prices[0];
//第二次卖出
// dp[0][4] = 0;
int i = 0;
while ( ++i < prices.length ){
//不买不卖永远为0
//第一次买入的钱 =
dp[i][1] = Math.max( dp[i-1][1], -prices[i] );
//第一次卖出的最大值，为 之前一天的买入的最大利润值 加上今天卖出 能挣到的 最大值 和 已有的最大值比较取较大的
dp[i][2] = Math.max( dp[i-1][2], dp[i-1][1] + prices[i] );
//第二次买入能得到的最大值，
//之前一天的卖出能赚取的最大值 减去当天买股票需要花掉的钱 同样和历史数据比较 取最大值
dp[i][3] = Math.max( dp[i-1][3], dp[i-1][2] - prices[i] );
//同理
//第二次卖出能赚取的最大利润
//前一天第二次买入能赚取的最大利润 + 今天卖出能赚的钱 一样历史数据中取最大值
dp[i][4] = Math.max( dp[i-1][4], dp[i-1][3] + prices[i] );
}
return Math.max(dp[--i][2],dp[i][4]);
}
}后面还有更多的股票问题变种以及非常类似的其他的粉刷房子系列的和打家劫舍系列的题面，如果感兴趣可以都尝试着做一下，这个问题上不再做更多的展开讨论了
系列2 ：粉刷房子
系列3 ：打家劫舍
虽然题型基本相同，不过再更多的练习中有助于提升归纳总结转移方程的能力
双串问题
双串问题应该是动态规划类型中出现得比较多的问题类型，而其中最常见又最有代表性的应当是字符串子序列相关的题目了
判断子序列 ，首先这个事一个简单题，作为双串问题的入手比较容易，我们就从这题开始
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？拿到这题的之后，我们最自然而然的想法其实应该是双指针的做法，顺便插一个双指针的解法，这能帮助我们接下来用动态规划的方法来处理之前，能更好的理解怎么得到这个动态规划的解法的
直接上代码了
class Solution {
public boolean isSubsequence(String s, String t) {
int idxS = -1;
int idxT = -1;
while (++idxS < s.length() && idxT < t.length()){
while (++idxT < t.length()){
if (s.charAt(idxS) == t.charAt(idxT)){
break;
}
}
}
return idxS == s.length() && idxT < t.length();
}
}具体思路如下：
- 在字符s和t上各一个指针
- 从各自字符串起始位置开始，在t中找s上当前对应的字符，如果不是则t上的指针往后移动一位
- 如果相同则s上之后往后移动一位，并t上的指针继续往后寻找当前s上的指向的字符
- 最终如果s上的指针到结尾了，则表明是包含的，时间复杂度：O(n+m)
在理清了上面的双指针思路后，我们试着想下如果用动态规划的方法该如何来做呢？我们建立一个dp[s.length+1][t.length+1]的数组，来标示状态。
横向的表示t字符串的情况，纵向的表示s字符串的情况，两者前面都加了一个为空的情况分析。如果你做过了不少双串动态规划问题的话，就会发现这种在前面额外加一个为空的情况是基本操作，会非常普遍的用到。另外一个最开始的dp[0][0]的值的定义也非常至关重要，会影响到你的整个二维滚动数组的运算操作。
直接拿官方示例来举例分析，自己画下这个矩阵就一下子一目了然、豁然开朗了。
a h b g d c
1 1 1 1 1 1 1
a 1 1 1 1 1 1
b 1 1 1 1
c 1分析过程
- 当
S串上为空的时候，他可以是任意T串的子序列 - 当
S串中多出了一个字符a,只有当T串有字符a的时候才能是他的子序列 - 当
S串中再次多出了一个字符b，只有当在T串中匹配到了字符b,且前面有字符a的时候才能成为T的子序列 - 再多了一个字符
c，操作步骤和之前的一样，最终可以确定abc是ahbgdc的子序列时间复杂度：O(m * n)
当然这里面还有其他的细节可以优化的地方，比如a匹配的时候记录下位置，下次到b的时候就从a第一次出现的位置往后遍历寻找
如果还没看明白的话，我们把需要查找的子串换下再试试
a h b g d c
1 1 1 1 1 1 1
b 1 1 1 1
d 0 1 1
a 0 0 0 0 0 0状态转移方程
//如果当前字符相等
dp[row][col] = dp[rol-1][col-1]
//如果字符不等
dp[row][col] = dp[rol][col-1]写份代码跑下试试，没毛病，
class Solution {
public boolean isSubsequence(String s, String t) {
boolean[][] dp = new boolean[s.length()+1][t.length()+1];
Arrays.fill(dp[0],true);
int row = 0;
while (++row<=s.length()){
int col = 0;{
while (++col<=t.length()){
dp[row][col] = s.charAt(row-1) == t.charAt(col-1)?dp[row-1][col-1]:dp[row][col-1];
}
}
}
return dp[s.length()][t.length()];
}
}以及状态压缩一维DP数组，需要借一个preStatus记录前一位下标在更新前的值，也许还有其他更好的写法，暂时没想出来，可以留言多多交流
class Solution {
public boolean isSubsequence(String s, String t) {
boolean[] dp = new boolean[t.length()+1];
Arrays.fill(dp,true);
int sIdx = -1;
boolean preStatus = true;
while (++sIdx<s.length()){
int tIdx = 0;
dp[0] = false;
preStatus = sIdx==0;
while (++tIdx <= t.length()){
boolean current = dp[tIdx];
dp[tIdx] = s.charAt(sIdx)==t.charAt(tIdx-1)?preStatus:dp[tIdx-1];
preStatus = current;
}
}
return dp[t.length()];
}
}相应的过程可以自行思考下是如何得到这个一维dp数组的操作的。
子序列匹配是一个应用非常普遍的算法，我们最常见的文章重复度查询，关键词匹配之类的就是最明显的示例了，既然说到了文章重复度查询，那么就让我们来看一下下面这一题
最长公共子序列 ，这个题目基本上属于学习动态规划必做题目之一了，热度非常的高
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。
如果不存在 公共子序列 ，返回 0 。 在有了前面一题的解题经验之后，面对这题，我相信你们应该能摸到一点点门路了，照样的，我们依旧建立一个二维dp[][]数组，横向的代表一个字符，纵向的代表另一个字符，且前面都留一个空代表为空的情况
以text1 = "qcssopd"，text2 = "abcsdku"为例，二维dp[][]数组中的每一个位置表示当前位置的时候能够得到的最长公共子序列的长度。
如下图，
- 第一行全是0，首先拿
q字符到abcsdku中寻找，结果没有 - 再次
qc的情况，我们发现有一个c字符可以匹配，那么从c字符的位置开始，之后的最长公共子序列长度应该是c，长度为1 - 接下来，重点情况。text1变换为“qcs”，text2从“a”依次增加到全长度，当text2的值为“abcs”的时候，我们可以知道末尾字符串字符相同，所以可以把这个问题转变为“qc”和“abc”的最长公共子序列的长度加1，而“qc”和“abc”的最长公共子序列长度我们在之前上一步3中已经得到了为1，所以此时的最长公共子序列长度为2。后面同理
- 如果末尾字符串不相等的情况，举例text1=“qcs”，text2=“abc”，这个情况可以转换为“qc”与“abc”的最长公共子序列或者“qcs”与“ab”的公共子序列中较大的一个。
- 后面依次循环执行3、4部分的逻辑
所以我们得到了状态转移方程
//当前字符相同的情况
dp[i][j] = dp[i-1][j-1]+1;
//当前字符不相同的情况
dp[i][j] = max( dp[i][j-1], dp[i-1][j]);相应的对应转移方程 的代码
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] dp = new int[text1.length()+1][text2.length()+1];
for (int row = 1; row <= text1.length(); row++) {
for (int col = 1; col <= text2.length(); col++) {
if (text1.charAt(row-1) == text2.charAt(col-1)){
dp[row][col] = dp[row-1][col-1]+1;
}else{
dp[row][col] = Math.max(dp[row-1][col],dp[row][col-1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}一个小问题，在最长公共子序列的长度的问题上再扩展一下，想要知道最长公共子序列是什么那么应该怎么办呢？在实现了上述算法之后其实就相应的很容易了，只需要在长度发生变化的时候把新增进来的字符记录下来即可。
接下来，让我们再看下下一题，困难题，不同的子序列
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。示例 1：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
[ b a ] b [ g ] b a g
[ b a ] b g b a [ g ]
[ b ] a b g b [ a g ]
b a [ b ] g b [ a g ]
b a b g [ b a g ]如果你对前面的2个问题已经能做到了完全掌握了的话，那么想要解出这题的话就不是什么太苦难的事情了，所谓困难不难，简单不易，困难的问题如果掌握了方法，也不会有难度，而简单的问题，因为看的角度不同思路不一样，实现的方法又多种多样，怎么样取舍达到最优解，又不是一个容易的事情。
好了，言归正传，我们回到题目上，还是一样拿题目中的示例来分析理解
下标: 0 1 2 3 4 5 6
b a b g b a g
b 1 1 2 2 3 3 3
a 1 1 1 1 4 4
g 1 1 1 5不管如何，我们先拿少量的数据先分析一下，得到如上这样的结果
- 当只有
b和babgbag字符串的时候，我们可以知道根据长度，的不同，可以得到不同的子序列情况，分别为下标[0,2,4]位置上的b字符相匹配，那么最终就是有3种情况。 - 当字符串从
b变成了ba之后，我们即时不知道规律，也可以凭自己的分析得到，可以有以下4种情况，
[ b a ] b g b a g
[ b ] a b g b [ a ] g
b a [ b ] g b [ a ] g
b a b g [ b a ] g当我们拿着a字符串babgbag上匹配的时候，来到了下标位置1，此时和下标1的a相等，那么我们就要往前一个状态看下，在b和b的时候有多少种情况，也就是左上角一格，这边可能还是不太明晰，我们继续往后走。
当走到下标位置5的时候，我们再次遇到了一个相同的a，这个时候捋一下，需要凑出ba子序列，这里使用了当前位置的a，而前面部分的b字符可以使用的情况就可以和左上角一格，也就是b在babgb中的子序列的情况总数，除了这部分之后，在使用当前5下标位置的a之前也可能有其他的a字符和他之前的b字符能组合起来合并成为ba组合的情况，那么，当前位置的情况总数应当是左上角的格子和本行前面一个格子的和。
3.先不忙着急结束，我们再看下第三行bag的情况，当拿着g字符到达下标3的时候遇到了相同的g，这个时候可以之前的ba与bab所在的左上角的数量1，加上bag与ba的数量0的和，就是1，再继续往后，到达了下标6，就等于左上角的4加上前面一格的1的和，也就是5
所以到了这个这里我们也就很明白对应的动规转移方程了。
//如果字符相等
dp[row][col] = dp[row-1][col-1] + dp[row][col-1]
//如果字符不相等
dp[row][col] = dp[row][col-1]代码如下：这里的代码中我们预设了一个空的第一行，和空的第一列，当为空的时候和第一列的空字符的子序列情况匹配，所以这一行都是1，当然你也可以在遍历滚动数组之前，实现就只有一个字符的情况遍历处理一遍，预处理b与babgbag的情况之后，再以这行数据为基础数据遍历这个滚动数组
class Solution {
public int numDistinct(String s, String t) {
int [][] dp = new int[t.length()+1][s.length()+1];
Arrays.fill(dp[0],1);
int row = 0;
while (++row < dp.length){
int col = row-1;
while (++col < dp[0].length){
if (t.charAt(row-1) == s.charAt(col-1)){
dp[row][col] = dp[row-1][col-1] + dp[row][col-1];
}else{
dp[row][col] = dp[row][col-1];
}
}
}
return dp[t.length()][s.length()];
}
}双串问题在动态规划中应该属于比较常见的，我们在这里暂时先告一段落，接下来让我们看下另一个问题类型
矩阵问题
三角形最小路径和 ，这个问题在前面我们已经讲过了，并以他为基础讲解了很多动态规划问题的基本概念知识，这里我们就先跳过了。
下降路径最小和 ，以及这一题，这两题基本是一模一样的，只是一个是三角形一个是矩形
最大正方形 ，这个问题就有点区别了，和这个问题相似的也有不少，我们来看一下
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。配图可能会更好理解一点
图中红色和绿色部分，都是只包含1的最大矩形。可能数据太小了，不好总结分析规律，不如我们自己再造一份数据分析一下看看，就一个3 x 4的全是1的数组吧
1 1 1 1
1 1 1 1
1 1 1 1 那么在这份数据上我们能得到如下的一份分析后的dp[][]二维数组，每个位置上的值表示以这个位置为右下角的话，能得到的最大正方形的边长。
1 1 1 1
1 2 2 2
1 2 3 3 - 首先一个先决条件，当前位置在入参的
char[][] matrix上的值是1 - 根据我们定义的特性，当前位置如果要成为某个正方形的右下角，那么作为必要条件，他的左边一格，上面一格，左上的格子都应当是边长大小相等的正方形，此时我们可以将这个位置设置为一个比前面这些正方形的边长大1的正方形，就如同上面的案例中第3行第1个出现的3一样
- 但是假如有其中一个小于了其他的值了呢？不妨还是再画一下看下，那么可以看到如果其中任意一个变小了，当前位置的矩形都会跟着变小
1 1 0 1
1 2 1 1
1 2 2 2 或者
1 0 1 1
1 1 1 2
1 2 2 2 那么我们就可以得到状态转移方程如下
//当前位置为0
dp[row][col] = 0
//当前位置为1
dp[row][col] = min( dp[row][col-1], dp[row-1][col], dp[row-1][col-1]) + 1下面是代码：
class Solution {
public int maximalSquare(char[][] matrix) {
int[][] dp = new int[matrix.length+1][matrix[0].length+1];
int max = 0;
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[row].length; col++) {
dp[row+1][col+1] = matrix[row][col]=='1'?Math.min(dp[row][col+1],Math.min(dp[row][col],dp[row+1][col]))+1:0;
max = Math.max(max,dp[row+1][col+1]);
}
}
return max*max;
}
}无串线性问题
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。示例：
输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。数据分析
第n个 0 1 2 3 4 5 6 7 8 9 10
数字 1 , 2 , 3 , 4 , 5 , 6 , 8 , 9 , 10 , 12
2 0 1 1 2 2 3 4 4 5 6
3 0 0 1 1 1 2 2 3 3 4
5 0 0 0 0 1 1 1 1 2 2可能不是看得太明白，这里我仔细讲下
- 初始1个
1 2、3、5分别和1相乘，得到结果2、3、5，其中2最小、2就是下一个丑数、且因为是2 x 1得来的，所以2对应的下标往后移动一位，到了12和当前对应的下标1的下一位2对应的数字2相乘结果为4，3、5依旧和自己对应的下标数字1相乘结果为3、5，其中最小的是3，则数字3对应的下标往后移动一位- 继续上面的逻辑，当前丑数是
3、则2、3、5与对应下标位置的丑数相乘的结果为4、6、5，最小的是2对应的结果4，下一个丑数就是4,2对应下标继续后移 - 继续这个步骤，后面省略数步，其中有一个特殊情况，如果两个数字的乘积都能对应下一个丑数，比如
2 x 3和3 x 2的情况，则这两个数的下标都往后移动一位
这个解法被很形象的赋予了一个名字三指针方法，2、3、5各自对应一个指针在整个丑数集合数组上，其本质还是动态规划，而且是那个不是很好理解的我到哪里去的动态规划解法。
代码如下
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int[] numArr = new int[]{2,3,5};
int[] pArr = new int[3];
for (int i = 1; i < n; i++) {
dp[i] = Math.min(Math.min(dp[pArr[0]]*numArr[0],dp[pArr[1]]*numArr[1]),dp[pArr[2]]*numArr[2]);
for (int p = 0; p < pArr.length; p++) {
if (dp[i] == dp[pArr[p]]*numArr[p]){
pArr[p] = pArr[p]+1;
}
}
}
return dp[n-1];
}
}如果此时你对这个思路已经非常明确的理解了，那么可以试试下面这题，丑数 II的升级版本超级丑数 ，题目内容我就不再重复了，就说一下区别，由原来的指定3个因数2、3、5变为了不确定多个因数int[] primes，解法思路也完全一样，动态规划即可。
01背包问题
下面我们将开始接触动态规划问题中最常见的最有意思的一个集合01背包问题，这个问题系列的内容其实很多，最基本的问题描述是这样的
假设你是一个小偷，此时你有一个容量为承重的背包，而在你的面前有n个物品，他们分别有重量和价值两个属性，
比如：
物品i的重量 W_i ，价值 V_i
问，在不超过背包容量的情况下，如何能拿到最大价值的物品总和背包问题分好几种情况，比如
1，要不要正好凑整背包重量
2，可选物品无限个还是有限个
篇幅原因，这里我们以其中一种情况距离讲解，如果对这个问题非常有兴趣，建议可以搜索下相关文章深入学习理解，最推荐的还是《背包九讲》系列，
空说不好理解，我们直接举个例子，以有限个数物品为例
此时有背包承重为5，
物品信息如下
W_1 = 1 V_1 = 1
W_2 = 2 V_2 = 3
W_3 = 3 V_3 = 6建立如下dp[][]数组
- 当背包容量为0 的时候，结果均为0
- 当背包容量为1的时候，只能放体积为1的物品，总价值最大为1
- 当背包容量为2的时候，如果只有物品1的情况下最大价值为1，当有了物品2，最大价值为3，那么这个3是怎么来的呢？尝试比较没有物品2时候，即
dp[1][2]的值，和有2的时候，把2的体积减去的价值+上2的价值，就是dp[2][0] + 3，选择其中较大的那个 - 后面省略数步，如果你对这个过程还是不太明确，不妨往后看看最后一步。当容量为5的时候，如果只有
1、2商品，可得最大占用体积为3、最大价值为4，此时加入了一个物品3，体积为3价值为6，那么试着看下当体积2的时候、没有物品3就是dp[2][2]加上物品3的价值6结果是9，两者比较，显然应该选择9
下面，我们来看一题具体的题目，零钱兑换 II ，零钱兑换系列在背包问题中用的非常普遍，
为了凑某个面值，硬币有限或者无限的情况，能不能凑出问题，能凑出几种情况问题，最少需要多少硬币问题等等，让我们直接看题吧
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1以需要凑出0到amount金额来处理，已有零钱面值为[1,2,5].png)
已知0元的情况，直接不用任何面值可以记为1种情况。
- 当我们有了面值为1的硬币之后，
- 如果一定要用面值为1的硬币的话，显然凑不出0元，只能使用原来只有0元的时候的情况
- 而如果面值大于0了，可以用当前面值减去面值为1的情况加一个硬币得来
- 当我们有了面值为2的硬币之后，
- 如果想要凑出面值小于2的情况，显然是不行的，只能用之前的方案代替
- 而大于等于2的时候，可以选择 前面的当前面值减去2元的情况加上一枚2元的硬币来组成 或者 之前没有2元面值的时候凑出2元的方案
- 到这里逻辑和
转移方程就都已经清楚了f [i][j] = f [i − 1][j] + f [i][j − x]
- 最后拿总额11来再说明下
- 可以是之前没有5元面值的时候凑出11元的方案
- 也可以是需要有5元面值硬币的时候凑出6元的方案加一个5元硬币.
我们把越界索引为负数的部分当做0处理
class Solution {
public int change(int amount, int[] coins) {
int [][] dp = new int[coins.length+1][amount+1];
dp[0][0] = 1;
for (int row = 1; row <= coins.length; row++) {
for (int col = 0; col <= amount; col++) {
dp[row][col] = dp[row-1][col] + (col>=coins[row-1]?dp[row][col-coins[row-1]]:0);
}
}
return dp[coins.length][amount];
}
}好了，到了这步了，你能否尝试状态压缩，改写成一维dp[]数组的实现呢？
背包问题的题型内容还有很多，强烈建议可以去看下《背包九讲》，而如果你对上面所讲的内容以及能够基本掌握了的话，动态规划问题就可以算是基本入门了。
额外补充部分，让我们看看另外一个题目
另类拓展题
接雨水 ， 这题看起来有点难，但是在理解了思路之后其实还是非常简单的
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 一开始做这题之前，我没有接触过动态规划，是用的单调队列的方法来实现的，不过这里让我们直接用动态规划的方法来看看这题吧
动态规划解法
某个位置能存储的最大雨量依赖于他的左侧的最大值和他右侧的最大值这两个值中的较小的一个值。那么怎么取到左侧的最大值和右侧的最大值呢？
- 从左往右依次比较保存最大值就是某个位置的左侧的最大值
- 从右往左依次比较保存最大值就是某个位置右侧的最大值
在这样的情况下，我们建立一个二维数组，new int[height.length][2]，其中dp[i][0]表示该位置左侧的最大值，dp[i][1]表示该位置右侧的最大值。这样对应的i位置能存储的最大水量就是
min(dp[i][0],dp[i][1])-height[i]转移方程已经确定的情况下那么代码也就非常容易写出来了
class Solution {
public int trap(int[] height) {
int count = 0;
int[][] dp = new int[height.length][2];
int idxLeft = 0;
int idxRight = height.length - 1;
dp[idxLeft][0] = height[idxLeft];
dp[idxRight][1] = height[idxRight];
idxLeft++;
idxRight--;
for (; idxLeft < height.length; idxLeft++) {
dp[idxLeft][0] = Math.max(dp[idxLeft-1][0],height[idxLeft]);
dp[idxRight][1] = Math.max(dp[idxRight+1][1],height[idxRight]);
if (idxLeft>=idxRight){
count += Math.min(dp[idxLeft][0],dp[idxLeft][1]) - height[idxLeft];
count += Math.min(dp[idxRight][0],dp[idxRight][1]) - height[idxRight];
}
idxRight--;
}
if (height.length%2==1){
int mid = height.length >> 1;
count -= Math.min(dp[mid][0],dp[mid][1]) - height[mid];
}
return count;
}
}这段代码，在一次遍历的过程中同时更新左侧的最大值和右侧的最大值，当两侧往中间靠拢的时候，如果在中间相遇了，那么就可以开始统计了。
后面有一段如果height数组长度为奇数，中间值会重复计算一遍所以需要减去
单调栈解法
作为对比，单调栈的解法和分析思路可以参考下
具体看这张图，找到第一个峰值，左边的都可以丢掉不管，因为第一个峰值左边的部分储不了水。从峰值开始，每个索引的值按照单调递减入栈，当有新的值比栈顶的值大的时候说明有开始呈上升趋势了，有开始上升的时候就说明这个时候是可以储水的了。
比如图中的索引4位置的值是3，当前栈内元素，按照从栈顶到栈底的顺序依次为1,4,5,7（实际栈内存的索引位置，后面默认都是不做额外说明）。
则可以计算得到A区域的面积，栈顶元素弹出，此时最新栈顶元素为4，而当前的3与4之间要储水的话，需要取小的一个，就是3，再减去之前弹出的栈顶元素1作为底部高度，那么这段区间可以储水面积就是3×1=3。并把3压入栈。
再往后到了索引5的位置，此时栈内元素为3,4,5,7。因为6大于3，把栈顶元素3出栈，按照之前同样的逻辑，6和此时栈顶的4比较取4，那么就得到了图中B区域的面积（4-3）x（5-2-1） = 2。继续和栈顶元素比较，6大于4，将4弹出，相同的操作，得到C区域的面积，同样的算出D区域的面积。最终将5位置6压入栈。
此时栈中元素为6,7。然后来到了索引6，索引6位置2小于此时小于栈顶的6，直接压入栈。之后到了索引7，再算出E，F区域的面积。最终即为所求总储水量。
class Solution {
int area = 0;
public int trap(int[] arr) {
if (null==arr||arr.length==0)return area;
int left = 0;
int index = 0;
//找出第一个左边
while (index < arr.length-1){
if (arr[index] >= arr[left]){
left = index;
}else{
break;
}
index++;
}
Deque<Integer> deque = new ArrayDeque<>();
deque.offer(left);
//此时的left一定是第一个最高点
for (int currentIndex = left; currentIndex < arr.length; currentIndex++) {
if (currentIndex > 0 && arr[currentIndex]>arr[currentIndex-1]){
while (!deque.isEmpty() && arr[currentIndex] >= arr[deque.peekLast()]){
int bottomIndex = deque.pollLast();
if (deque.isEmpty()){
break;
}
int leftIndex = deque.peekLast();
int height = Math.min(arr[currentIndex],arr[leftIndex]) - arr[bottomIndex];
int width = currentIndex - leftIndex - 1;
area += height * width;
}
}
deque.offerLast(currentIndex);
}
return area;
}
}
发表评论