# 动态规划算法实战

## 1. 一维DP

### 1.1 题目1：买卖股票的最佳时机

输入: [7,1,5,3,6,4]



输入: [7,6,4,3,1]



$F[x]=max(F[x-1],nums[x]-minVal)$

class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0: return 0
dp = [0] * n
minVal = prices[0]

for i in range(1, n):
minVal = min(minVal, prices[i])
dp[i] = max(dp[i - 1], prices[i] - minVal)

return dp[-1]


### 1.2 题目2：打家劫舍

输入: [1,2,3,1]



输入: [2,7,9,3,1]



• $F[x]$：小偷偷窃到 x 位置的房屋为止，且最后偷窃 x 位置的房屋，此时偷窃的最大金额值
• $M[x]$：小偷偷窃到 x 位置的房屋为止，且最后没有偷窃 x 位置的房屋，此时偷窃的最大金额值

\begin{aligned} &F[x] = M[x-1] + nums[x]\\ &M[x] = max(F[x-1], M[x-1]) \end{aligned}

$result = max(F[-1], M[-1])$

class Solution:
def rob(self, nums):
if not nums:
return 0
# 初始条件
F = [0] * len(nums)
M = [0] * len(nums)

# 初始条件
F[0] = nums[0]
M[0] = 0
for i in range(1, len(nums)):
# 得到状态转移方程
F[i] = M[i - 1] + nums[i]
M[i] = max(F[i - 1], M[i - 1])
# 返回最后结果
return max(F[-1], M[-1])


## 2. 二维 DP

### 2.1 题目1：不同路径

$P[i][j]=P[i-1][j] + P[i][j-1]$

\begin{aligned} &P[i][0]=1(i=0,\cdots,m)\\ &P[0][j]=1(j=0,\cdots,n) \end{aligned}

class Solution:
def uniquePaths(self, m, n):
if not m or not n:
return 0

P = []
# 保证 P[i][0]=1,P[0][j]=1，即可。其余位置将会递推得到
for i in range(m):
P.append([1] * n)

# 动态转移方程
for i in range(1, m):
for j in range(1, n):
P[i][j] = P[i-1][j] + P[i][j-1]

return P[-1][-1]



### 2.2 题目2：最长公共子序列(LCS)

输入：text1 = "abcde", text2 = "ace"



输入：text1 = "abc", text2 = "abc"



输入：text1 = "abc", text2 = "def"



• $P[i][j]$：表示 text1[0:i] 和 text2[0:j] 的最长公共子序列的长度。

LCS的状态矩阵示意图

\begin{aligned} &P[i][j]=P[i-1][j-1]+1(text1[i]==text2[j]) \\ &or \; max(P[i-1][j], P[i][j-1])(text1[i]!=text2[j]) \end{aligned}

class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
if not text1 or not text2:
return 0

# 初始状态矩阵
P = []
for _ in range(len(text1)):
P.append([0] * len(text2))

# 编写初始状态，以下两个for循环主要是处理一些边界问题
for j in range(len(text2)):
if j == 0:
P[0][j] = 1 if text2[j] == text1[0] else 0
else:
P[0][j] = max(P[0][j-1], 1 if text2[j] == text1[0] else 0)

for i in range(len(text1)):
if i == 0:
P[i][0] = 1 if text1[i] == text2[0] else 0
else:
P[i][0] = max(P[i-1][0], 1 if text1[i] == text2[0] else 0)

# 核心部分，状态转移方程
for i in range(1, len(text1)):
for j in range(1, len(text2)):
# 上面图片中推到的状态转移方程
if text1[i] == text2[j]:
P[i][j] = P[i-1][j-1] + 1
else:
P[i][j] = max(P[i-1][j], P[i][j-1])

return P[-1][-1]