动态规划如何测试是否超时？
动态规划法（dynamic programming）通常用于求解最优化问题（optimization problem），它适用于那些子问题相互重叠的情况，即子问题不独立，不同的子问题具有公共的子子问题（就是子问题的子问题）。这显然与分治法是不同的，分治法将问题划分为不重叠的子问题，然后分别求解这些子问题，最后将这些问题合并得到最终的解。
对于具有公共子问题的情况，分治法会做很多不必要的工作，它会多次求解同一子子问题。动态规划法却不一样，对每个子子问题它只会求解一次，将其保存在一个表格中，避免了不必要的重复计算。
利用动态规划法求出来的是这个问题的一个最优解（an optimal solution），记住这里求解的只是最优解（the optimal solution）中的一个，因为最优解可能有多个。
适用dp的问题必须满足最优化原理和无后效性。
1.最优化原理：如果问题的最优解包含的子问题的解也是最优解，则称该问题具有最有子结构，即满足最优化原理。（也即子结构最优时通过选择后一定最优）
2.无后效性：某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响，简单的说，就是“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。
3.重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）。其实本质上dp就是一个以空间换时间的做法，为了降低时间复杂度，不对子问题进行重复计算，其必须存储过程中的各种状态。
动态规划可以从暴力枚举逐步优化得到。问题求解的各个方法:暴力枚举->递归->备忘录算法->动归算法
[leetcode]10.Regular Expression Matching
对于p字符串有点、字母、点.
.
、字母?
?
四种元素，点匹配任意一个字母，字母匹配相同的一个字母，点?
?
匹配任意字母（可以是任意不同字母，例如.?
.
?
匹配abc），字母?
?
匹配连续任意个相同字母，值得注意的是?
?
的任意包括0个。由于?
?
可以匹配任意个，造成检验s和p是否完全匹配的时候难以确定究竟?
?
匹配几个字母合适，这正是本题的关键点。
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
# dynamic programming
len_s = len(s)
len_p = len(p)
# initialize
dp = [[False for i in range (len_p+1)] for j in range(len_s+1)]
dp[0][0] = True
# initialize dp[0][j]
for j in range(1,len_p):
if p[j] == '*':
dp[0][j+1] = dp [0][j-1]
for i in range(1,len_s+1):
for j in range(1,len_p+1):
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = (dp[i-1][j-2] and (p[j-2] == s[i-1] or p[j-2] == '.')) or dp[i][j-2] or
(dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] =='.'))
return dp[len_s][len_p]
相似的题目还有：[leetcode]44.Wildcard Matching;
[leetcode]62.Unique Paths
动态规划的关键是要得到递推关系式。对于本题，到达某一点的路径数等于到达它上一点的路径数与它左边的路径数之和。也即，起点到点(i, j)的路径总数：ways[i][j] = 起点到点(i, j-1)的总数：ways[i][j-1] + 起点到点(i-1, j)总数：ways[i-1][j]。于是我们就得到递推关系式：????????[??][??]=????????[??][???1]+????????[???1][??]
w
a
y
s
[
i
]
[
j
]
=
w
a
y
s
[
i
]
[
j
?
1
]
+
w
a
y
s
[
i
?
1
]
[
j
]
class Solution:
def uniquePaths(self, m, n):
paths = [[1 for i in range(n)] for i in range(m)]
for i in range(1,m):
for j in range(1,n):
paths[i][j] = paths[i-1][j]+paths[i][j-1]
return paths[m - 1][n - 1]
相似的题目还有：[leetcode]63.Unique Paths II;[leetcode]64.Minimum Path Sum
[leetcode]72.Edit Distance
编辑距离也是一个极其重要和经典的问题了。
这个算法计算的是将s[1…i]转换为t[1…j]（例如将kitten转换为sitting）所需最少的操作数（也就是所谓的编辑距离），这个操作数被保存在d[i,j]（d代表的就是上图所示的二维数组）中。
在第一行与第一列肯定是正确的，这也很好理解，例如我们将kitten转换为空字符串，我们需要进行的操作数为kitten的长度（所进行的操作为将kitten所有的字符丢弃）。
我们对字符可能进行的操作有三种：
如果我们可以使用k个操作数把s[1…i]转换为t[1…j-1]，我们只需要把t[j]加在最后面就能将s[1…i]转换为t[1…j]，操作数为k+1
如果我们可以使用k个操作数把s[1…i-1]转换为t[1…j]，我们只需要把s[i]从最后删除就可以完成转换，操作数为k+1
如果我们可以使用k个操作数把s[1…i-1]转换为t[1…j-1]，我们只需要在需要的情况下（s[i] != t[j]）把s[i]替换为t[j]，所需的操作数为k+cost（cost代表是否需要转换，如果s[i]==t[j]，则cost为0，否则为1）。
将s[1…n]转换为t[1…m]当然需要将所有的s转换为所有的t，所以，d[n,m]（表格的右下角）就是我们所需的结果。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m,n = len(word1),len(word2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i==j==0:
dp[0][0] = 0
elif i==0:
dp[0][j] = j
elif j==0:
dp[i][0] = i
else:
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
return dp[-1][-1]
[leetcode]91.Decode Ways
很显然，由于本题只要求有多少种decode的方法，而不要求把每种方法都列出来，所以用DP。假设当前的元素为Z，他前面的两个为XY， i.e.XYZ。
1.如果Z=0, 并且Y=1 or 2。 那么对应于Z的DP值等于X的DP值，因为对于10只有一种解释方式，所以 DP[i] = DP[i-2]。
2.如果 YZ 位于[11, 19] 或者 [21, 26] 这两个range中，那么显然对于这个两位数我们有两种decode的方式，也就是说 DP[i] = DP[i-1]+DP[i-2], 注意这里不是DP[i] = DP[i-1]+1。 例如 1212中的最后一个2。
3.如果X不是0， 例如YZ = 81。 那么DP[i] = DP[i-1].
最后注意的是由于2中我们要取到DP[i-2]，所以我们在初始DP list的时候在最前面加上一个1。由于加上了最前面的这个1。所以当DP[i]对应的是s[i-1]。 YZ对应的就是 s[(i-1)-1:(i-1)+1]。
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
dp = [1 for i in range(len(s)+1)]
for i in range(2,len(s)+1):
nums = s[i-2:i]
if 1<int(nums)<10 :
dp[i] = dp[i-1]
elif 11<=int(nums)<=19 or 21<=int(nums)<=26:
dp[i] = dp[i-1]+dp[i-2]
elif int(nums) == 10 or int(nums) == 20:
dp[i] = dp[i-2]
elif nums[-1]=='0':
dp[i] = 0
else:
dp[i] = dp[i-1]
return dp[-1]
[leetcode]97.Interleaving String
可以用递归做，每匹配s1或者s2中任意一个就递归下去。但是会超时。
因此考虑用动态规划做。
s1, s2只有两个字符串，因此可以展平为一个二维地图，判断是否能从左上角走到右下角。
当s1到达第i个元素，s2到达第j个元素:
地图上往右一步就是s2[j-1]匹配s3[i+j-1]。
地图上往下一步就是s1[i-1]匹配s3[i+j-1]。
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if not s1:return s2==s3
if not s2:return s1==s3
m,n = len(s1),len(s2)
if m+n != len(s3):return False
dp = [[False for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i==j==0:
dp[i][j] = True
elif i == 0:
dp[0][j] = (dp[0][j-1] and s2[j-1] == s3[j-1])
elif j == 0:
dp[i][0] = (dp[i-1][0] and s1[i-1] == s3[i-1])
else:
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
return dp[m][n]
[leetcode]115.Distinct Subsequences
互异子序列。用dp[i][j]记录S的前i个和T的前j个的符合个数，那么最后目标就是dp[S.size()][T.size()];
初始化，j = 0 时候，dp[i][0] = 1，因为所有的都可以通过删除所有变成空字符，并且只有一种。
递推式子如下了：
i和j都从1开始，且j不能大于i，因为匹配的长度至少为1开始，j大于i无意义
如果 ??==??
i
==
j
那么 dp[i][j] = S.substr(0, i) == T.substr(0, j);
如果 ??!=??
i
!
=
j
分两种情况
S[i-1] != T[j-1] 时，也就是加入不加入i的影响是一样的，那么 dp[i][j] = dp[i - 1][j];
S[i-1] == T[j-1] 时，那么当前字符可选择匹配或者是不匹配，所以dp[i][j] = dp[i - 1][j -1] + dp[i - 1][j];
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m,n = len(s),len(t)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
dp[0][0] = 1
for j in range(1,m+1):
dp[0][j] = 1
for i in range(1,n+1):
for j in range(1,m+1):
if t[i-1] == s[j-1]:
dp[i][j] = dp[i-1][j-1]+dp[i][j-1]
else:
dp[i][j] = dp[i][j-1]
return dp[n][m]
[leetcode]123.Best Time to Buy and Sell Stock III
这道是买股票的最佳时间系列问题中最难最复杂的一道，前面两道 Best Time to Buy and Sell Stock 和 Best Time to Buy and Sell Stock II 的思路都非常的简洁明了，算法也很简单。而这道是要求最多交易两次，找到最大利润，还是需要用动态规划Dynamic Programming来解，而这里我们需要两个递推公式来分别更新两个变量local和global.我们其实可以求至少k次交易的最大利润，找到通解后可以设定 k = 2，即为本题的解答。我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])
其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值中取较大值，而全局最优比较局部最优和前一天的全局最优，代码如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
# 二维数组
# k = 2
# local = [[0 for j in range(k+1)] for i in range(len(prices))]
# glob = [[0 for j in range(k+1)] for i in range(len(prices))]
# for i in range(1,len(prices)):
# diff = prices[i]-prices[i-1]
# for j in range(1,k+1):
# local[i][j] = max(local[i-1][j]+diff,glob[i-1][j-1]+diff)
# glob[i][j] = max(glob[i-1][j],local[i][j])
# return glob[-1][-1]
# 一维数组
k = 2
local = [0 for j in range(k+1)]
glob = [0 for j in range(k+1)]
for i in range(1,len(prices)):
diff = prices[i]-prices[i-1]
for j in reversed(range(1,k+1)):
local[j] = max(local[j]+diff,glob[j-1]+diff)
glob[j] = max(glob[j],local[j])
return glob[-1]
其实可以总结为两个状态的DP，分别代表当天必须卖的利润和不一定当天卖的利润。
[leetcode]132.Palindrome Partitioning II
输入一个字符串，将其进行分割，分割后各个子串必须是“回文”结构，要求最少的分割次数。显然，为了求取最少分割次数，一个简单的思路是穷尽所有分割情况，再从中找出分割后可构成回文子串且次数最少的分割方法。
对于一个字符串，我们需要考虑所有可能的分割，这个问题可以抽象成一个DP问题，对于一个长度为n的字符串，设DP[i][j]表示第i个字符到第j个字符是否构成回文，若是，则DP[i][j]=1;若否，则DP[i][j]=0
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = [(i-1) for i in range(n + 1)]
for i in range(n + 1):
for j in range(i):
tmp = s[j:i]
if tmp == tmp[::-1]:
dp[i] = min(dp[i], dp[j] + 1)
return dp[n]
[leetcode]139.Word Break
动态规划。dp[i]表示字符串s[:i]能否拆分成符合要求的子字符串。我们可以看出，如果s[j:i]在给定的字符串组中，且dp[j]为True（即字符串s[:j]能够拆分成符合要求的子字符串），那么此时dp[i]也就为True了。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False for i in range(len(s)+1)]
dp[0] = True
for i in range(len(s)+1):
for k in range(i):
if dp[k] and s[k:i] in wordDict:
dp[i] = True
# break
return dp[len(s)]
以上关于字符串的动态规划，我们可以发现：对于字符串求最长/短，最大/小的最优解，我们可以通过分析子问题来分解问题的求解，通过子问题的求解来完成整体的最优解。
[leetcode]174.Dungeon Game
自底向上的动态规划
在走完最后一个房间的时候血量至少要剩下１，因此最后的状态可以当成是初始状态，由后往前依次决定在每一个位置至少要有多少血量, 这样一个位置的状态是由其下面一个和和左边一个的较小状态决定 ．因此一个基本的状态方程是: dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j].
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
dp = [[0 for j in range(n)]for i in range(m)]
for i in reversed(range(m)):
for j in reversed(range(n)):
if i == m-1 and j == n-1:
dp[i][j] = max(0, -dungeon[i][j])
elif i == m-1:
dp[i][j] = max(0, dp[i][j+1] - dungeon[i][j])
elif j == n-1:
dp[i][j] = max(0, dp[i+1][j] - dungeon[i][j])
else:
dp[i][j] = max(0, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
return dp[0][0] + 1
[leetcode]198.House Robber
动态规划DP。本质相当于在一列数组中取出一个或多个不相邻数，使其和最大。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:return 0
dp = [0 for i in range(len(nums)+1)]
for i in range(1,len(nums)+1):
if i==1:
dp[1] = nums[0]
else:
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[-1]
[leetcode]213.House Robber II
这个题多了环的条件，在这个约束下就多了个不同时偷第一个和最后一个就可以了。所以，两种偷的情况：第一种不偷最后一个房间，第二种不偷第一个房间，求这两种偷法能获得的最大值。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:return 0
elif len(nums)==1:return nums[0]
elif len(nums)==2:return max(nums[0],nums[1])
else:
return max(self._rob(nums[1:]),self._rob(nums[:-1]))
def _rob(self,nums):
if not nums:return 0
dp = [0 for i in range(len(nums)+1)]
dp[1] = nums[0]
for i in range(2,len(nums)+1):
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[-1]
[leetcode]221.Maximal Square
动态规划，令A[i][j]表示的就是以(i,j)为右下角的最大的正方形的边长，时间复杂程度是??(?????)
O
(
M
?
N
)
，空间复杂程度是??(?????)
O
(
M
?
N
)
。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:return 0
m,n = len(matrix),len(matrix[0])
dp = [[0 for j in range(n)] for i in range(m)]
res = 0
for i in range(m):
for j in range(n):
if i == 0:
dp[i][j] = int(matrix[i][j])
elif j == 0:
dp[i][j] = int(matrix[i][j])
else:
if matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j- 1],dp[i-1][j],dp[i][j- 1])+1
else:
dp[i][j] = 0
res = max(res,dp[i][j])
return res*res
注意这里dp[i][j]的更新条件是，matrix[i][j] == '1'，更新为dp[i-1][j- 1],dp[i-1][j],dp[i][j- 1]的最小值+1
[leetcode]309.Best Time to Buy and Sell Stock with Cooldown
两个状态：
１．在第i天买一支股票还能剩下的利润＝第(i-2)天销售能够剩余的利润－第i天股票的价钱．
２．在第i天卖一支股票总的利润＝第(i-1)天买股票剩下的最大利润＋当前股票的价格．
也就是说需要维护两个状态的信息，一个是买股票所得到的剩余最大利润，一个是卖出股票之后得到的最大利润，他们互相依赖对方的信息．
再来进一步分析如何维持一个最大的利润．
对于买来说，当天是否买取决于买了之后是否比之前买所剩余的利润大，即状态转移方程为：
buy[i] = max(buy[i-1], sell[i-2] - prices[i-1]);
对于卖来说，同样当天是否将这只股票卖掉取决于卖掉能否获得更大的利润，状态转移方程为：
sell[i] = max(sell[i-1], buy[i-1] + prices[i-1]);
也可以根据题意，维护三个状态，更容易理解。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# if not prices:
# return 0
# N = len(prices)
# buy = [0 for i in range(N+1)]
# sell = [0 for i in range(N+1)]
# buy[1] = -prices[0]
# for i in range(2,N+1):
# buy[i] = max(sell[i-2]-prices[i-1],buy[i-1])
# sell[i] = max(sell[i-1],buy[i-1]+prices[i-1])
# return sell[N]
if not prices:
return 0
N = len(prices)
rest = [0 for i in range(N)]
buy = [0 for i in range(N)]
sell = [0 for i in range(N)]
buy[0] = -prices[0]
for i in range(1,N):
rest[i] = max(rest[i-1],sell[i-1])
buy[i] = max(buy[i-1],rest[i-1]-prices[i])
sell[i] = max(sell[i-1],buy[i-1]+prices[i])
return sell[-1]
[leetcode]312.Burst Balloons
动态规划
设dp[i][j]为i到j这段区间所能得到的最大值，状态转移方程为dp[i][j] = max(i < k < j) (dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
n = len(nums)
dp = [[0 for j in range(n)] for i in range(n)]
# dp[i][j]代表(i,j)区间内取得的最大值 -->关键在于理解dp内涵
for left in reversed(range(n)):
for right in range(left+1,n):
for i in range(left + 1, right):
dp[left][right] = max(dp[left][right],nums[left] * nums[i] * nums[right] +dp[left][i] + dp[i][right])
return dp[0][-1]
[leetcode]368.Largest Divisible Subset
使用一个一维DP，其含义是题目要求的数组，DP[i]的含义是，从0~i位置满足题目的最长数组。先用i遍历每个数字，然后用j从后向前寻找能被nums[i]整除的数字，这样如果判断能整除的时候，再判断dp[i] < dp[j] + 1，即对于以i索引结尾的最长的数组是否变长了。在变长的情况下，需要更新dp[i]，同时使用parent[i]更新i的前面能整除的数字。另外还要统计对于整个数组最长的子数组长度。
知道了对于每个位置最长的子数组之后，我们也就知道了对于0~n区间内最长的满足题目条件的数组，最后需要再次遍历，使用parent就能把正儿个数组统计输出出来。因为这个最大的索引mx_index是对n而言的，所以输出是逆序的。
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums: return []
N = len(nums)
nums.sort()
dp = [1] * N #LDS
parent = [0] * N
mx = 1
mx_index = -1
for i in range(N):
for j in reversed(range(i)):
if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
parent[i] = j
if dp[i] > mx:
mx = dp[i]
mx_index = i
res = []
for k in range(mx):
res.append(nums[mx_index])
mx_index = parent[mx_index]
return res[::-1]
这里的解题技巧是，在动态规划同时保存状态，并且使用额外空间恢复现场。
[leetcode]486.Predict the Winner
动态规划
1.该问题没有直接比较一个选手所拿元素的和值，而是把问题转换为两个选手所拿元素的差值。这一点很巧妙，是关键的一步。
2.找出递推表达式：max(nums[beg] - partition(beg + 1, end), nums[end] - partition(beg, end + 1))
3.通过递推表达式构造递归算法是比较简单的。但是要构造一个非递归的算法难度较大。对于非递归算法，首先在dp中赋初始值，这是我们解题的第一步。在这个问题中，我们使用一个二位的数组dp来表示nums数组中任意开始和结束位置两人结果的差值。
初始的时候，我们仅仅知道对角线上的值。dp[i][i] = nums[i].这一点很好理解。接下来既然是求任意的开始和结束，对于二维数组，那肯定是一个双层的循环。通过dp中已知的元素和动态规划的递推表达式，我们就可以构造出我们的需要的结果。非递归的方式是从小问题到大问题的过程。
class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
dp_f = [[0 for j in range(n)] for i in range(n)]
dp_g = [[0 for j in range(n)] for i in range(n)]
for i in reversed(range(n)):
for j in range(i,n):
if i==j:
dp_f[i][j] = nums[i]
else:
dp_f[i][j] = max(nums[i]+dp_g[i+1][j],
nums[j]+dp_g[i][j-1])
dp_g[i][j] = min(dp_f[i+1][j],dp_f[i][j-1])
return dp_f[0][-1] >= sum(nums)/2
[leetcode]494.Target Sum
该问题求解数组中数字只和等于目标值的方案个数，每个数字的符号可以为正或负(减整数等于加负数)。由于target和sum(nums)是固定值，因此原始问题转化为求解nums中子集的和等于sum(P)的方案个数问题，可转化为背包问题求解。
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
sum_ = sum(nums)
target = (sum_+S)/2
if target!=int(target):
return 0
if target>sum(nums):
return 0
target = int(target)
dp = [0 for i in range(target+1)]
dp[0] =1
for num in nums:
for i in reversed(range(num,target+1)):
dp[i] += dp[i-num]
return dp[-1]
[leetcode]516.Longest Palindromic Subsequence
设立一个len行len列的dp数组～dp[i][j]表示字符串i～j下标所构成的子串中最长回文子串的长度～最后我们需要返回的是dp[0][len-1]的值。
dp数组更新：首先i指针从尾到头遍历，j指针从i指针后面一个元素开始一直遍历到尾部～一开始dp[i][i]的值都为1，如果当前i和j所指元素相等，说明能够加到i～j的回文子串的长度中，所以更新dp[i][j] = dp[i+1][j-1] + 2; 如果当前元素不相等，那么说明这两个i、j所指元素对回文串无贡献，则dp[i][j]就是从dp[i+1][j]和dp[i][j-1]中选取较大的一个值即可。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
if not s:
return 0
n = len(s)
dp = [[0 for j in range(n)] for i in range(n)]
for i in reversed(range(n)):
for j in range(i,n):
if i == j:dp[i][j] = 1
elif s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][-1]
[leetcode]576.Out of Boundary Paths
这道题给了我们一个二维的数组，某个位置放个足球，每次可以在上下左右四个方向中任意移动一步，总共可以移动N步，问我们总共能有多少种移动方法能把足球移除边界，由于结果可能是个巨大的数，所以让我们对一个大数取余。那么我们知道对于这种结果很大的数如果用递归解法很容易爆栈，所以最好考虑使用DP来解。那么我们使用一个三维的DP数组，其中dp[k][i][j]表示总共走k步，从(i,j)位置走出边界的总路径数。那么我们来找递推式，对于dp[k][i][j]，走k步出边界的总路径数等于其周围四个位置的走k-1步出边界的总路径数之和，如果周围某个位置已经出边界了，那么就直接加上1，否则就在dp数组中找出该值，这样整个更新下来，我们就能得出每一个位置走任意步数的出界路径数了，最后只要返回dp[N][i][j]就是所求结果了。
class Solution:
def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
dp = [[0] * n for _ in range(m)]
for s in range(1, N + 1):
curStatus = [[0] * n for _ in range(m)]
for x in range(m):
for y in range(n):
v1 = 1 if x == 0 else dp[x - 1][y]
v2 = 1 if x == m - 1 else dp[x + 1][y]
v3 = 1 if y == 0 else dp[x][y - 1]
v4 = 1 if y == n - 1 else dp[x][y + 1]
curStatus[x][y] = (v1 + v2 + v3 + v4) % (10**9 + 7)
dp = curStatus
return dp[i][j]
背包问题
[leetcode]322.Coin Change
使用动态规划，需要构建一个长度是amount + 1的dp数组，其含义是能够成面额从0到amount + 1需要使用的最少硬币数量。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [float('inf') for i in range(amount + 1)]
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
# if dp[i - coin] != float('inf'):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount]!= float('inf') else -1
[leetcode]474.Ones and Zeroes
这道题是从字符串集合中尽可能多的选出字符串并保证0和1个数不超过给定值，题目难度为Medium。
题目和0-1背包问题大同小异，区别是这里限制0和1个数，而0-1背包问题限制总重量，算是动态规划的经典题目。
这里用dp[i][j][k]表示前i个字符串在0个数不超过j、1个数不超过k时最多能选取的字符串个数。统计第i个字符串中0和1个数分别为cnt0和cnt1，如果取第i个字符串则dp[i][j][k] = dp[i-1][j-cnt0][k-cnt1] + 1，如果不取第i个字符串则dp[i][j][k] = dp[i-1][j][k]，取两者大的作为dp[i][j][k]的值。由于dp[i][j][k]只与dp[i-1][*][*]相关，所以这里可以重复使用?????
m
?
n
个数据将空间复杂度降为??(?????)
O
(
m
?
n
)
，只需在遍历时从后向前遍历即可。具体代码：
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0 for j in range(n+1)] for i in range(m+1)]
for str in strs:
cnt0 = str.count('0')
cnt1 = str.count('1')
for i in reversed(range(cnt0,m+1)):
for j in reversed(range(cnt1,n+1)):
dp[i][j] = max(dp[i][j],dp[i-cnt0][j-cnt1]+1)
return dp[-1][-1]
[leetcode]518.Coin Change 2
建立dp数组，保存能到达当前amount的步数。逐个金额遍历，看只用前i个金额能到达j的步数有多少，实现方法是累加起来dp[当前amount - 第i个金额]，最后返回dp[amount]。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0 for i in range(amount+1)]
dp[0] = 1
for coin in coins:
for i in range(coin,amount+1):
dp[i] += dp[i-coin]
return dp[-1]
总结
对于常见的动态规划问题，有以下实例：
1.斐波那契数列(Climbing Stairs)
2.01背包问题
3.最长公共子序列
4.旅行商问题 n!
Attention：
动态规划算法用到的题目存在很多套路
滚动数组，状态压缩，（升维，单调性，四边形不等式（高级套路））
本质：先暴力，找冗余，去冗余
版权说明：Copyright © 广州京杭网络科技有限公司 2005-2024 版权所有 粤ICP备16019765号
广州京杭网络科技有限公司 版权所有
免费热线：400-683-0016
扫二维码关注公众号
当前位置：