【一起学算法】咬文嚼字的动态规划
上篇文章有个地方写错了，不知道大家发现没？--||
本篇80%内容参考《算法之道》
本篇主要内容：
什么是动态规划？
从问题分析递归/记忆化递归/动态规划
最优子结构/重复子问题
leetcode实战
回想一下，上次计算斐波那契数列时，我们按起递归的定义进行求解，将fi b(n)分解成fib(n-1)和fib(n-2)，一直递归到fib(0)和fib(1),但这种分治效率并不高，因为需要计算大量同样的项，其渐进趋势为指数级O(2^n)。（想一想在递归调用的这个过程中fib(1)...fib(n-1)分别被计算了多少次？）
（图片来自leetcode）
但如果采用自底向上（Bottom Up）的策略,从fib(0),fib(1)开始，按照fib(0),fib(1),...,fib(n)的顺序一个个计算，就可以避免重复，获得线性级效率！
这种自底向上构建大问题解答的方案就是这次要写的动态规划策略。
什么是动态规划
动态规划使用的是一种更有针对性的分而治之的策略，其英文名是Dynamic Programming，但这里的Programing和编程没有关系，而是指表格查询法（Tabular Method），即：将每一步计算的结果存储在表格里，供随后的计算查询。
说到这里，动态规划与分治策略之间的不同已经清楚了，动态规划，我们将原问题分解成小问题，但分解的小问题有许多是重复的！这样用表格将计算出来的结果存起来可以减少重复计算。但这一点还不是动态规划的全部，动态规划被提出来的目的在于优化，不仅要解决一个问题，而是要以最优的方式解决这个问题！
由此我们得到动态规划的特点如下：
分析一个最优解决方案应该具备的结构
递归定义最优解决方案
由底至上构建一个最优解决方案
从问题分析递归/记忆化递归/动态规划
首先我们来总结一下提到过n遍的斐波那契数列
裸递归：如同上图中那颗递归树可见，我们可以看到会重复计算很多次fib(3),fib(2),它的时间复杂度是O(2^n)
class Solution(object):def fib(self, N):""":type N: int:rtype: int"""if N==0:return 0if N==1:return 1return self.fib(N-1)+self.fib(N-2)
记忆化递归：既然我们调用递归的时候重复计算了很多次fib(3),fib(2),那是不是可以考虑一旦计算出fib(m)的结果，就将这个结果记住，例如存入一个数组memory[]，这样我们减少重复计算，时间复杂度可以达到O(n)。
class Solution:def fib(self, N: int) -> int:if N==0:return 0if N==1:return 1memo=[None]*(N+1)memo[0]=0memo[1]=1def fibb(n):if memo[n]!=None :return memo[n]else:memo[n]=fibb(n-1)+fibb(n-2)return memo[n]return fibb(N)
动态规划：自底向上，先存入fib(0),fib(1),再按递推顺序得到并存入fib(3),fib(4),...,fib(n)。（某种程度上，我觉得它不涉及到一个最优子结构只能算一个递推，但它确实解决了重复计算的问题。）
class Solution:def fib(self, N: int) -> int:if N==0:return 0if N==1:return 1dp=[None]*(N+1)dp[0]=0dp[1]=1for i in range(2,N+1):dp[i]=dp[i-1]+dp[i-2]return dp[N]
再看最优路径的情况。
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例：
输入:[[1,3,1],[1,5,1],[4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。
递归：
因为每次只能向下或向右，那么对于位置(i,j)，它只能由(i-1,j)和(i,j-1)走过来。cost(m,n)=min(cost(m-1,n),cost(m,n-1))+grid[ij]因此生成如下递归树：
虽然才画三层，但已经可以看见有重复的计算出现。
class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m=len(grid)n=len(grid[0])def cost_func(i,j):if i==0 and j==0:return grid[i][j]if i==0 and j>0:return cost_func(i,j-1)+grid[i][j]if i>0 and j==0:return cost_func(i-1,j)+grid[i][j]if i-1>=0 and j-1>=0:return min(cost_func(i-1,j),cost_func(i,j-1))+grid[i][j]return cost_func(m-1,n-1)
结果严重超时。。
记忆化递归：记住已经计算过的位置。
class Solution:def minPathSum(self, grid: List[List[int]]) -> int:m=len(grid)n=len(grid[0])memo=[[None]*n for _ in range(m)]def cost_func(i,j):if memo[i][j]!=None:return memo[i][j]if i==0 and j==0:memo[i][j]=grid[i][j]if i==0 and j>0:memo[i][j]=cost_func(i,j-1)+grid[i][j]if i>0 and j==0:memo[i][j]=cost_func(i-1,j)+grid[i][j]if i-1>=0 and j-1>=0:memo[i][j]=min(cost_func(i-1,j),cost_func(i,j-1))+grid[i][j]return memo[i][j]return cost_func(m-1,n-1)
瞬间过了时间点！
动态规划：
考虑状态转移方程cost[i][j]=min(cost[i-1][j],cost[i][j-1])+grid[i][j]
初始状态：起始点cost[0][0]，行列的边界cost[0][i],cost[i][0]
自底向上计算
import numpy as npclass Solution(object):def minPathSum(self, grid):""":type grid: List[List[int]]:rtype: int"""m=len(grid)n=len(grid[0])dp=np.zeros((m,n),int)dp[0][0]=grid[0][0]for i in range(1,n):dp[0][i]=grid[0][i]+dp[0][i-1]for j in range(1,m):dp[j][0]=grid[j][0]+dp[j-1][0]for i in range(1,m):for j in range(1,n):dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]return dp[m-1][n-1]
现在对动态规划已经有一些理解了吗？
对最优路径的应用，在隐马尔可夫模型中，我们用到维特比算法，就是基于此种动态规划。基于观测时间序列生成最有可能的隐含状态序列。详情参考李航《统计学习方法》。
最优子结构/重复子问题
经过了上述的例子，可以窥见动态规划要能成功，需要注意原问题的两点：
最优子结构
重复子问题
因此在考虑使用动态规划策略时，我们的一般战略如下：
证明问题的解决方案中包括一个选择，选择之后将留下一个或多个子问题。
设计子问题的递归描述方式。
证明对原问题的最优解里包括对所有子问题的最优解。
证明子问题之间重叠。
c点保证了动态规划的正确性，d点保证了动态规划时间复杂度的优越性。
在设计一个动态规划时，我们需要去找到它的状态转移方程，以及初始状态。
leetcode实战
（系好安全带，现在要加速了）
下面我将给三个leetcode的例子
一维dp leetcode32最长有效括号(hard)
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例1：
输入: "(()"输出: 2解释: 最长有效括号子串为 "()"
示例2:
输入: ")()())"输出: 4解释: 最长有效括号子串为 "()()"
解析：
dp[i]将表示以s[i]结尾的字符串中最长有效括号子串长度
状态转移方程：
我们知道只用当s[i]=')'时才有可能产生以s[i]结尾的最长有效括号
这时考虑怎么到达s[i],有两种情况：
s[i-1]='(' 那么这时构成了一对有效的(),因此：
dp[i]=dp[i-2]+2
s[i-1]=')'那么这时问题就比较复杂，因为dp[i-1]对应了以s[i-1]结尾的最长有效括号子串，这时我们需要去找到这个有效子串的前一个字符。
pre=i-dp[i-1]-1
当这个pre是'('时，则又构成了一对，此时还可能连接上以s[pre-1]结尾的有效括号子串
dp[i]=dp[i-1]+2+dp[pre-1]
注意边界条件不要出界。
初始状态：
dp[0]=0,若s[0]='(',s[1]=')',则dp[1]=1,其余dp[1]=0
class Solution(object):def longestValidParentheses(self, s):""":type s: str:rtype: int"""#dp[i]表示以i结尾的最大字符串长度n=len(s)if n<=1:return 0dp=[0]*nif s[0]=="(" and s[1]==")":dp[1]=2for i in range(2,n):if s[i-1]=='(' and s[i]==')':dp[i]=dp[i-2]+2if s[i-1]==")" and s[i]==")":pre=i-dp[i-1]-1if pre>=0 and s[pre]=="(" and pre-1>=0:dp[i]=dp[i-1]+2+dp[pre-1]elif pre>=0 and s[pre]=="(" and pre-1<0:dp[i]=dp[i-1]+2res=max(dp)return res
二维dp leetcode1143最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例1：
输入：text1 = "abcde", text2 = "ace"输出：3解释：最长公共子序列是 "ace"，它的长度为 3。
示例2:
输入：text1 = "abc", text2 = "abc"输出：3解释：最长公共子序列是 "abc"，它的长度为 3。
dp[i][j]表示text1包含前i个字符的子串和text2包含前i个字符的子串的最长公共子序列
状态转移方程：
当text1[i]==text2[j]时，则dp[i][j]=dp[i-1][j-1]+1
当不等于时，则dp[i][j]=max(dp[i-1][j],dp[i][j-1])
初始状态：
要考虑子串为""时的情况，当text1的子串为空时即dp[0][i],这时是没有公共子序列的，因此dp[0][i]=0,同理dp[i][0]=0。
class Solution(object):def longestCommonSubsequence(self, text1, text2):""":type text1: str:type text2: str:rtype: int"""m=len(text1)n=len(text2)dp=[[0]*(n+1) for _ in range(m+1)]for i in range(1,m+1):for j in range(1,n+1):if text1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])return dp[m][n]
三维dp leetcode123 买卖股票的最佳时机：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入: [3,3,5,0,0,3,1,4]输出: 6解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例2:
输入: [3,3,5,0,0,3,1,4]输出: 6解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
(i,k,s)表示第i天，最多操作了k次，是s表示此时状态，若此时没有持有股票则s=0,若此时手里持有股票则s=1,dp[i][k][s]表示在这样的情况下的最大盈利。当买入时，我们就记录操作+1了一次。
状态转移方程：
第i天，最多操作了k次的情况下，此时手里没有持有股票，可能是前一天持有卖掉了股票，也有可能是前一天没有持有股票：
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+price[i])
此时手里持有股票，可能是前一天持有股票，在这里没有改变，也有可能是前一天没有股票，在这里买入了。
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-price[i])
初始状态：
考虑在没有任何操作时，没持有股票则：
dp[i][0][0]=0
而持有股票的情况时不可能的则：
dp[i][0][1]=-inf
在第0天时，没持有股票则：
dp[0][k][0]=0
持有股票则是买入了第0天的股票：
dp[0][k][1]=-price[0]
class Solution:def maxProfit(self, prices: List[int]) -> int:if len(prices)<2:return 0k=2n=len(prices)dp=[[[[],[]] for _ in range(k+1)] for _ in range(n)]for i in range(n):dp[i][0][0]=0dp[i][0][1]=float('-inf')for i in range(n):for j in range(1,k+1):if i==0:dp[i][j][0]=0dp[i][j][1]=-prices[i]else:dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i])dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])return dp[n-1][k][0]
当然动态规划远不如这么简单，那么祝好运了！