动态规划思路
参考
状态转移方程：
明确「状态」-> 定义dp数组/函数的含义 -> 明确「选择」-> 明确 base case
试题
53最大子序和
题目描述
53
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
题解思路
思路一
我可以这么想pd[i]表示指针一直扫到i时目前存在的连续区间的最大和。那就不需要记录每个以nums[i]结尾的连续区间最大和，即上面代码注释那里。我们直接取pd[i]不就时我们想要的结果了吗。
指针指到i后的状态：
- 我们将nums[i]作为连续区间末尾
- 我们不将nums[i]作为连续区间末尾
由此想到，改变的量不只是i还有是否将nums[i]作为末尾，所以还有一个变量或者我理解成选择，于是pd[i]变成pd[i][0], pd[i][1]，其中0代表不将nums[i]作为结尾，1代表将nums[i]作为结尾。
dp[i][0]含义： 到nums[i]为止，不以nums[i]为结尾，前面连续区间和的最大值。dp[i][1]类似。
状态转移方程
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) # 不以nums[i]结尾，那最大的就是前面i-1两种情况中一个
dp[i][1] = max(dp[i-1][1]+nums[i], nums[i]) #以i结尾
base case
dp[0][0] = -inf # 这里不选0结尾，那最大和为什么不是0，是为了防止nums[0]<0，那么dp[1][0] = 0而不是nums[0]出错
dp[0][1] = nums[0]
题解
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [[0]*2]*len(nums)
dp[0][0] = float("-inf")
dp[0][1] = nums[0]
for i in range(1, len(nums)):
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = max(dp[i-1][1]+nums[i], nums[i])
return max(dp[len(nums)-1][0], dp[len(nums)-1][1])
这里其实不需要dp[i][0]，因为这道题里，最大情况只会存在于pd[i][1]里(因为假设最大情况以nums[i]结尾，那最大的就是Pd[i][1])。而pd[i][1]与pd[i][0]毫无关系，所以不需要计算pd[i][0]，状态转移方程：pd[i] = max(pd[i-1]+nums[1], nums[i])，这里循环的同时，将nums扫过的部分看作pd[i]，更新。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i] = max(nums[i-1]+nums[i], nums[i])
return max(nums)
64最小路径和
题目描述
64
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
题目思路
明确状态dp的含义，dp[i][j]：从左上角走到(i,j)处，路劲数字和最小为dp[i][j]
两种选择，右或下，就造成dp[i][j]由下面两种结果得到
状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + nums[i][j]
base case: 这里的初始化比较复杂点，因为当i或j=0时，在状态转移方程里出现了 i-1=-1，j-1=-1这肯定是不可能的。所以要初始化dp[i][0]以及dp[0][j]
这里的初始化也好初始化，因为dp[i][0]只能是从dp[0][0]一路往下走，dp[0][j]同样从dp[0][0]一路往右走。 带pd数组的迭代法，自下而上，一般递归是自上而下。
题解
# 战胜99.74 %的方法
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [[0 for i in range(n)] for j in range(m)]
dp[0][0] = grid[0][0]
for i in range(1,m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,n):
dp[0][i] = dp[0][i-1] + grid[0][i]
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]
这道题遇到的问题
dp = [[0 for i in range(n)] for j in range(m)] 这句话我一开始写的是 dp = [[0]n]m，这样是绝对不行的。因为这种 ， 一旦改变一个值所有都变了。比如
a = [[0]*5]*5
a[0][0] = 1
print(a)
输出：
[[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0]]
所以在pytohn里初始化一个多维数组，最好用[[0] for i in range(n)]这种。
优化
由dp[i][j] = dp[i-1][j] + dp[i][j-1]可知，当我们计算第i行的值的时候是不需要1~i-2行的值，那么只需要一个一维数组保存上一行的信息即可。
dp[i] = dp[i] + dp[i-1]，每次从左到右更新dp，这里的dp[i-1]就是i左边那一格，等号后面的dp[i]还没更新，是上一行第i列的值。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [0 for i in range(n)]
dp[0] = grid[0][0]
#初始化第0行的值
for i in range(1,n):
dp[i] = dp[i-1] + grid[0][i]
for i in range(1,m):
dp[0] = dp[0] + grid[i][0]
for j in range(1,n):
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
return dp[n-1]
72. 编辑距离(hard)
题目描述
72
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
题目思路
状态定义
每个阶段状态pd[i][j]，定义为word1长度为i，word2长度为j，将word1变成word2需要的最小操作数。
注意，这里我们只专注于操作数， pd[i][j]可以理解成word1[:i]变成word2[:j]需要的操作数。
选择
我们遍历两个单词每个字符，如果word1[i]==wordr2[j]，那么什么都不需要做。pd[i][j] = pd[i-1][j-1]，i,j两个字符就被排除了，只需要算剩下的字符。
如果不相等，有三种选择：
- 插入，在word1 i处插入word2[j]。即 dp[i][j] = dp[i][j-1] + 1
- 删除，删除word1[i]，即 dp[i][j] = 1 + dp[i-1][j]
- 替换， dp[i][j] = dp[i-1][j-1] + 1
综上，只需要取dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
Base case
当i或j为0时，有一个单词长度为0，自然只能不断删除或者插入。需要两个for循环来初始化pd[i][0]和pd[0][j]的值。
题解
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [[0 for i in range(m+1)] for j in range(n+1)] #注意单词长度从0~len(word1)所以要+1
for i in range(1, n+1):
dp[i][0] = dp[i-1][0] + 1
for i in range(1, m+1):
dp[0][i] = dp[0][i-1] + 1
for i in range(1,n+1):
for j in range(1,m+1):
if word1[i-1] == word2[j-1]: # 这里也要注意下标要-1
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
return dp[n][m]
优化
同上题一样，可以画图观察dp[i][j]需要那些量，发现dp[i][j]只与dp[i-1][j] , dp[i-1][j-1] , dp[i][j-1]相关。与之前不同的是，这里多了个dp[i-1][j-1]需要额外的变量保存，不然我们更新了dp[i-1]再来计算dp[i]就得不到上一行的i-1处的值，然而这又是我们需要的，所以额外用一个变量保存即可。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
dp = [j for j in range(m+1)] #注意单词长度从0~len(word1)所以要+1
for i in range(1,n+1):
temp = dp[0]
dp[0] = i
for j in range(1,m+1):
pre = temp
temp = dp[j]
if word1[i-1] == word2[j-1]: # 这里也要注意下标要-1
dp[j] = pre
else:
dp[j] = min(dp[j-1], dp[j], pre) + 1
return dp[m]
64. 最小路径和
64
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
dp[i][j]:表示到(i,j)的最小路径和
那么怎么才能到达(i,j)处呢，有两种要么从(i-1,j)要么从(i,j-1)走来。所以：dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]。
优化
我们发现这个二维dp数组的值取决于，左边的值和上面的值。dp[1][j]第一行的值也就取决于dp[0][j]和dp[1][j-1]，我们只需要维护一个一维数组即可。
从第0行开始，初始化一个dp[j]，那么dp[j] = dp[j-1] + grid[j]，因为第0行只能往右边走。
第1行：dp[j] = min(dp[j], dp[j-1]) + grid[j]，因为一开始dp[j]还没有更新所以他保留的是上一行的值，相当于dp[i-1][j]。这里的dp[j-1]相当于dp[i][j-1]。因此，状态转移方程为：dp[j] = min(dp[j], dp[j-1]) + grid[j]。
BaseCase: 我们需要初始化第一行。
题解
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [0 for i in range(n)]
dp[0] = grid[0][0]
#初始化第0行的值
for i in range(1,n):
dp[i] = dp[i-1] + grid[0][i]
for i in range(1,m):
dp[0] = dp[0] + grid[i][0]
for j in range(1,n):
dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
return dp[n-1]
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
思路同上题
题解
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] for i in range(n)]
for i in range(n):
dp[i] = 1
for i in range(1,m):
for j in range(1,n):
dp[j] = dp[j-1] + dp[j]
return dp[n-1]
343. 整数拆分
343
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
因为题目要求是，至少拆为2个，并使他们乘积最大。
状态： 乘积。我们用dp[i]表示整数i拆分后的最大乘积。
选择：怎么得到dp[i]的？假设i拆成，j和i-j两个数。那么直观上dp[i] = dp[j] * dp[i-j]。这里有一个错误，dp[j]不一定比j大，因为题目必须让我们拆成至少两个数再乘，如果dp[j]比j小，那还不如j就不拆了，dp[i] = j * dp[i-j]。例如 2拆成 1 * 1 = 1 < 2。所以dp[i]改进后:
状态转移方程： dp[i] = max(dp[j], j) * max(dp[i-j], i-j)。
class Solution:
def integerBreak(self, n: int) -> int:
num = n+1
dp = [0 for i in range(num)]
for i in range(2, num):
temp = 1
for j in range(1, i):
temp = max(temp,max(dp[j], j) * max(dp[i-j],i-j))
dp[i] = temp
return dp[n]
这里我犯了一个错误，没有temp，直接dp[i] = max(temp,max(dp[j], j) * max(dp[i-j],i-j)),所以没有保存下最大值。
第 k 个数
有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
示例 1:
输入: k = 5
输出: 9
这里的数的因子只能是3,5,7的组合。
我们发现，从1开始下一个数就是min(1*3, 1*5, 1*7)，在下一个就是min(3*3, 1*5, 1*7)，为什么只考虑min(3*3, 1*5, 1*7)，不考虑3*5, 3*7呢？
因为我们的数列是从小到大的，很明显后面的数3乘以5和7肯定大于前面的数1乘以5和7。所以不用考虑3*5, 3*7。
因此发现，用三个指针分别从左往右扫，三个指针分别代表要将指向的数乘以3或5或7，每次我们选择当前最小值即可。
状态转移方程
pd[i] = min(dp[p1]3, dp[p2]5, dp[p3]*7)，这里p1只负责将它指向的数乘以3，同理p2,p3分别代表乘以5和7。这三个指针都从左往右扫描数组。
题解
class Solution:
def getKthMagicNumber(self, k: int) -> int:
dp = [1]
p1,p2,p3 = 0,0,0
for i in range(k-1):
Min = min(dp[p1]*3, dp[p2]*5, dp[p3]*7)
dp.append(Min)
if dp[p1]*3==Min: p1+=1
if dp[p2]*5==Min: p2+=1
if dp[p3]*7==Min: p3+=1
return dp[k-1]
32. 最长有效括号
题目描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解题思路
状态，好定义。dp[i]表示以第i个字符结尾的最长有效括号。结尾一般是')'结尾。
选择，即怎么得到dp[i]。因为我们只考虑s[i]==')'的情况，所以：
当s[i]=')'时，若s[i-1]='('，则dp[i] = dp[i-2]+2
若s[i-1]=')'，若s[i-1-dp[i-1]]='('，则dp[i] = d[i-1] + 2 + dp[i-2-dp[i-1]] #将s[i-1-dp[i-1]]之前的字符也考虑在内，所以加上dp[i-2-dp[i-1]]，稍微想想就明白
Base Case，都为0。这道题要注意判断条件。
题解
class Solution:
def longestValidParentheses(self, s: str) -> int:
# dp初始化为0
# 当s[i]=')'时，若s[i-1]='('，则dp[i] = dp[i-2]+2
# 若s[i-1]=')'，若s[i-1-dp[i-1]]='('，则dp[i] = d[i-1] + 2 + dp[i-2-dp[i-1]]
# 边界条件=号判断再想想
dp = [0 for i in range(len(s))]
for i in range(1,len(s)):
if s[i]==')':
if s[i-1]=='(':
# 这里不用判断i-2>=0的原因是，因为只有i=1时，i-2才会小于0也就是-1，
# 然而dp[-1]=0的，所以不用管。之后i-2都大于或等于0
dp[i] = dp[i-2] + 2
# i-1-dp[i-1]就是指向了与 s[i]相对应的那个有效顺括号当然要判断它是否大于等于0以及他是否等于'('，
# 如果不能同时满足这两个条件，那么dp[i]=0，也就值不变
elif i-1-dp[i-1]>=0 and s[i-1-dp[i-1]]=='(':
# 这里dp[i-2-dp[i-1]]也就是之前的值了，也要判断下是否大于或等于0，否则不加上他
dp[i] = dp[i-1] + 2 + dp[i-2-dp[i-1]] if i-2-dp[i-1]>=0 else dp[i-1] + 2
if dp:
return max(dp)
else:
return 0
1143. 最长公共子序列
题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
状态:dp[i][j]，text1[:i]与text2[:j]最长公共子序列
选择：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])
同样可以优化成一个以维dp数组解决，同上面的编辑距离优化问题：
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# dp[i][j] ：text1[:i] 与 text2[:j]最长公共子序列
# 如果text1[i] == text2[j] , dp[i][j] = dp[i-1]dp[j-1] + 1
# 其他 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
dp = [0 for i in range(len(text2)+1)]
for i in range(1,len(text1)+1):
temp = dp[0]
for j in range(1,len(dp)):
pre = temp
temp = dp[j]
if text1[i-1]==text2[j-1]:
dp[j] = pre + 1
else:
dp[j] = max(dp[j], dp[j-1])
return dp[len(text2)]
注意这里保存dp[i-1][j-1]的操作，再第一层循环初始化temp = dp[0], 第二层pre = temp; temp = dp[j]这样就可以下次循环仍能取到上次的dp[j-1]的值。