动态规划（二）
动态规划问题的的一般思路：
（数学归纳思想）
判别问题是否具有最有子结构
找到base case，通过状态转移关系确认每一步的状态转换，定义dp数组的含义
主要难点在于
状态转移方程的确立；dp数组的定义，怎么表达每一步的状态转换。
（如对于两个字符串的问题，首先考虑二维dp数组）
递归 自顶向下：确认最小规模问题的解，由原问题向下逐级分解规模，然后逐层返回答案。通常会产生大量重叠子问题，通过记录每个子问题的解优化（如备忘录）
动态规划 自底向上：与递归相反，由最小规模问题一步步向上推直到求出原问题的解。
编辑距离问题：
误区：纠结于字符串灵活修改插入删除忽略最优子结构特性
base case：任一数组为空
状态转移：
状态：指针的移动 选择：删除插入修改跳过
dp数组定义：【s1长度】【s2长度】 由下标记录子问题的解
1 class Solution: 2 def minDistance(self, word1: str, word2: str) -> int: 3 s1 = len(word1) + 1 4 s2 = len(word2) + 1 5 dp = [[0] * s2 for _ in range(s1)] 6 for i in range(s1): 7 dp[i][0] = i 8 for i in range(s2): 9 dp[0][i] = i 10 for i in range(1, s1): 11 for j in range(1, s2): 12 if word1[i-1] == word2[j-1]: 13 dp[i][j] = dp[i - 1][j - 1] 14 else: 15 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1) 16 return dp[s1-1][s2-1]
最长回文序列：
难点：dp数组的定义 遍历方向
思考怎样同过dp数组的定义能够表达状态转移方程，状态转移需要归纳思维，说白了就是如何从已知的结果推出未知的部分。
本题中，求一个数组的最长回文序列可以由 除去头尾元素 除去头（尾）元素的子数组的最长回文序列得到当前数组的解，由此启发dp数组的定义。
思考：dp数组维度和问题指针个数
数组遍历的方向要保证正确的状态转移，由已知推位置。
1 class Solution: 2 def longestPalindromeSubseq(self, s: str) -> int: 3 n = len(s) 4 dp = [[0] * n for _ in range(n)] 5 for i in range(n - 1, -1, -1): 6 dp[i][i] = 1 7 for j in range(i + 1, n): 8 if s[i] == s[j]: 9 dp[i][j] = dp[i + 1][j - 1] + 2 10 else: 11 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 12 return dp[0][n - 1]si
思考最长回文子序列另一思路：把字符串翻转求两字符串最长公共子序列
状态压缩：
如果计算dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩技巧。
说白了，就是降低dp数组维度（“投影” 增加变量储存被覆盖的值），从而降低空间复杂度。缺点是往往代码可读性也会变差。
以最小插入次数构造回文串：
思路类似于最长回文序列，主要处理好状态转移。
1 class Solution: 2 def minInsertions(self, s: str) -> int: 3 lenth = len(s) 4 dp = dp = [[0] * (lenth + 1) for _ in range(lenth + 1)] 5 for i in range(lenth - 1, 0, -1): 6 for j in range(i + 1, lenth + 1): 7 if s[i-1] == s[j-1]: 8 dp[i][j] == dp[i + 1][j - 1] 9 else: 10 dp[i][j] == min(dp[i + 1][j], dp[i][j - 1]) + 1 11 return dp[1][lenth]
动态规划之正则表达式：
思路上还是比较容易的，本质上还是字符串匹配的问题，状态转移在于通配符的选择上。
要想到的是 在这个问题当中，相比dp数组，递归函数更便于体现状态转移
1 class Solution: 2 def isMatch(self, s: str, p: str) -> bool: 3 m, n = len(s), len(p) 4 5 def matches(i: int, j: int) -> bool: 6 if i == 0: 7 return False 8 if p[j - 1] == '.': 9 return True 10 return s[i - 1] == p[j - 1] 11 12 f = [[False] * (n + 1) for _ in range(m + 1)] 13 f[0][0] = True 14 for i in range(m + 1): 15 for j in range(1, n + 1): 16 if p[j - 1] == '*': 17 f[i][j] |= f[i][j - 2] 18 if matches(i, j - 1): 19 f[i][j] |= f[i - 1][j] 20 else: 21 if matches(i, j): 22 f[i][j] |= f[i - 1][j - 1] 23 return f[m][n]
原文地址：http://www.cnblogs.com/edych/p/16815325.html
