本文目录
基本思想
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的。
动态规划一般可以分为以下几个步骤：
- 分析最优解的性质，并刻画其结构特征；
- 递归地定义最优解；
- 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值；
- 根据计算最优值时得到的信息，构造问题的最优解。
常见题目
爬楼梯
class Solution:
def climbStairs(self, n: int) -> int:
# if n == 1:
# return 1
# dp = [0]*(n+1) # dp[i]表示n=i时方法的种类
# dp[1], dp[2] = 1, 2
# for i in range(3, n+1):
# dp[i] = dp[i-1] + dp[i-2]
# return dp[n]
# 不利用数组
a = b = 1
for _ in range(n):
a, b = b, a+b
return a
不同路径
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if n == 1 and m == 1:
return 1
# 矩阵中的元素初始化为1
# matrix[i-1][j-1] 表示到达位置（i,j)的路径数
matrix = [[1]*n for i in range(m)]
for i in range(1, m):
for j in range(1, n):
matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
return matrix[m-1][n-1]
最大正方形
class Solution:
# dp[i][j] 代表在以i, j这一格为右下角的正方形边长。
# 如果这一格的值也是1，那这个正方形的边长就是他的上面，左手边，和斜上的值的最小边长 + 1。
# 因为如果有一边短了缺了，都构成不了正方形。
def maximalSquare(self, matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dp = [[0 if matrix[i][j] == '0' else 1 for j in range(
0, n)] for i in range(0, m)]
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
else:
dp[i][j] = 0
res = max(max(row) for row in dp)
return res ** 2
三角形最小路径和
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# 原地修改triangle
# triangle[i][j]表示到达第i行第j列的最小路径和
rows = len(triangle)
if rows == 1:
return triangle[0][0]
for row in range(1, rows):
for col in range(row+1):
self.helper(triangle, row, col)
return min(triangle[-1])
def helper(self, triangle, n, i):
if i == 0:
triangle[n][i] += triangle[n-1][0]
elif i == n:
triangle[n][i] += triangle[n-1][-1]
else:
triangle[n][i] += min(triangle[n-1][i-1], triangle[n-1][i])
零钱兑换
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 动态规划, dp[i]表示amount为i时的最少硬币个数
dp = [0] + [float('inf') for i in range(amount)]
for i in range(1, amount+1):
for c in coins:
if i-c >= 0:
dp[i] = min(dp[i], dp[i-c]+1)
return dp[-1] if dp[-1] != float('inf') else -1
零钱兑换 II
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# dp[i]表示amount = i时的硬币组合数
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for j in range(c, amount + 1):
dp[j] += dp[j - c]
return dp[amount]
打家劫舍
class Solution:
def rob(self, nums) -> int:
if not nums:
return 0
# dp[i]表示到 第i个房屋能够盗窃到的最大金额
# 注意初始化dp[0] 为0, dp[1]为nums[0]
n = len(nums)
dp = [0]*(n+1)
dp[1] = nums[0]
for i in range(2, n+1):
dp[i] = max(dp[i-2]+nums[i-1], dp[i-1])
return dp[-1]
打家劫舍 II
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
elif len(nums) <= 3:
return max(nums)
else:
return max(self.rob_helper(nums[1:]), self.rob_helper(nums[:-1]))
def rob_helper(self, nums):
res = [0]*len(nums)
res[0], res[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
res[i] = max(res[i-1], res[i-2]+nums[i])
return res[-1]
打家劫舍 III
class Solution:
def rob(self, root: TreeNode) -> int:
return self.helper(root, dict())
def helper(self, root, memo):
if not root:
return 0
if root in memo:
return memo[root]
val = root.val
if root.left:
val += self.helper(root.left.left, memo)
val += self.helper(root.left.right, memo)
if root.right:
val += self.helper(root.right.left, memo)
val += self.helper(root.right.right, memo)
memo[root] = max(
val,
self.helper(root.left, memo)+self.helper(root.right, memo)
)
return memo[root]
完全平方数
class Solution:
def numSquares(self, n: int) -> int:
# 动态规划（超时）
# if n <= 0:
# return 0
# dp = [float('inf')]*(n+1) # dp[i]表示组成i的完全平方数的最小个数
# dp[0] = 0
# for i in range(1, n+1):
# j = 1
# while j*j <= i:
# dp[i] = min(dp[i], 1+dp[i-j*j])
# j += 1
# return dp[-1]
# BFS，像树状图一样进行分解
if n <= 0:
return 0
i, squares = 1, []
while i*i <= n:
squares.append(i*i)
i += 1
s, count = {n}, 0
while s:
count += 1
temp = set()
for num in s:
for y in squares:
if num - y == 0:
return count
elif num - y > 0:
temp.add(num-y)
else:
break
s = temp
return count
单词拆分
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# dp[i] 代表s[:i+1]可以被拆分成字典中的单词
dp = [False]*(len(s)+1)
dp[0] = True
for i in range(len(s)):
for j in range(i, len(s)):
if dp[i] and s[i:j+1] in wordDict:
dp[j+1] = True
return dp[-1]
丑数 II
class Solution:
def nthUglyNumber(self, n: int) -> int:
ugly = [1]
i2 = i3 = i5 = 0
while len(ugly) < n:
while ugly[i2]*2 <= ugly[-1]:
i2 += 1
while ugly[i3]*3 <= ugly[-1]:
i3 += 1
while ugly[i5]*5 <= ugly[-1]:
i5 += 1
ugly.append(min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5))
return ugly[-1]
编辑距离
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
size1, size2 = len(word1), len(word2)
# dp[i][j]表示word1[:i]转化到word2[:j]所需的最少操作
dp = [[0]*(size2+1) for _ in range(size1+1)]
for i in range(size2+1):
dp[0][i] = i
for i in range(size1+1):
dp[i][0] = i
for i in range(1, size1+1):
for j in range(1, size2+1):
if word1[i-1] == word2[j-1]:
tmp = dp[i-1][j-1]
else:
tmp = dp[i-1][j-1] + 1
dp[i][j] = min(tmp, dp[i-1][j]+1, dp[i][j-1]+1)
return dp[-1][-1]
最长上升子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 动态规划 O(n^2)
# if not nums:
# return 0
# dp = [1] * len(nums)
# for i in range(len(nums)):
# for j in range(i):
# if nums[i] > nums[j]:
# dp[i] = max(dp[i], dp[j] + 1)
# return max(dp)
# 利用二分查找 O(nlogn)
# tails[k]表示长度为k的递增子序列的最小的尾数
tails, res = [0]*len(nums), 0
for n in nums:
i, j = 0, res
while i < j:
mid = (i+j)//2
if tails[mid] < n:
i = mid + 1
else:
j = mid
tails[i] = n
if j == res:
res += 1
return res