前言
本篇博客记录本人在LeetCode上练习动态规划算法的记录，分为简单、中等、困难三个等级，每次刷题记录也都会附上时间，方便阅览。
简单
[2022/10/4 : 7道]
【509. 斐波那契数】
原题链接：https://leetcode.cn/problems/fibonacci-number/
代码
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
a1, a2, a3 = 0, 0, 1
for i in range(2, n + 1):
a1, a2 = a2, a3
a3 = a1 + a2
return a3
【1137. 第 N 个泰波那契数】
原题链接：https://leetcode.cn/problems/n-th-tribonacci-number/
代码
class Solution:
def tribonacci(self, n: int) -> int:
if n == 0:
return 0
if n <= 2:
return 1
x, y, z = 0, 1, 1
for i in range(3, n + 1):
s = x + y + z
x, y, z= y, z, s
return s
【70. 爬楼梯】
原题链接：https://leetcode.cn/problems/climbing-stairs/
思路：
首先初始化，到第一层楼梯可以爬一个阶梯，有一种方式，爬第二层可以一次爬一个台阶，也可以爬两个，有两种方式。此后的第N层楼梯既可由N-2台阶爬两次，也可以由N-1层楼梯爬一个台阶获得，则递推关系式:
f ( x ) = { 1 x = 1 2 x = 2 f ( x ? 1 ) + f ( x ? 2 ) x ≥ 3 f(x)= \begin{cases} 1 & x = 1\\ 2 & x = 2\\ f(x-1)+f(x-2) & x \geq 3\\ \end{cases} f(x)=? ? ??12f(x?1)+f(x?2)?x=1x=2x≥3?
代码
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 2
for i in range(3, n + 1):
c = a + b
a, b = b, c
return c
【118. 杨辉三角】
原题链接：https://leetcode.cn/problems/pascals-triangle/
代码
class Solution:
def generate(self, n) -> List[List[int]]:
res = []
for i in range(1, n + 1):
tmp = [0 for _ in range(i)]
res.append(tmp)
for i in range(n):
res[i][0], res[i][i] = 1, 1
for i in range(2, n):
for j in range(1, i):
res[i][j] = res[i - 1][j] + res[i - 1][j - 1]
return res
【119. 杨辉三角 II】
原题链接：https://leetcode.cn/problems/pascals-triangle-ii/
代码
class Solution:
def getRow(self, n: int) -> List[int]:
res = []
for i in range(1, n + 2):
tmp = [0 for _ in range(i)]
res.append(tmp)
for i in range(n + 1):
res[i][0], res[i][i] = 1, 1
for i in range(2, n + 1):
for j in range(1, i):
res[i][j] = res[i - 1][j] + res[i - 1][j - 1]
return res[n]
【121. 买卖股票的最佳时机】
原题链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
思路：
在一次遍历中，保存价格的最小值，再依次算当天股票价格与最低价格的差值，取最大，即买卖股票的最佳时机。
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
minn = max(prices)
profit = 0
for i in prices:
minn = min(i, minn)
profit = max(i - minn, profit)
return profit
【338. 比特位计数】
原题链接：https://leetcode.cn/problems/counting-bits/
思路：
1的二进制表示1，2的二进制表示10，3的二进制表示为11，4的二进制表示为100，5的二进制表示为101，5%2=1 5的二进制表示1的个数等于2的二进制表示1的个数加5%2，可以得到递推关系式： f ( x ) = f ( x / 2 ) + x % 2 f(x)=f(x/2)+x\%2 f(x)=f(x/2)+x%2
代码
class Solution:
def countBits(self, n: int) -> List[int]:
f = [0 for i in range(n + 1)]
for i in range(n + 1):
f[i] = f[i // 2] + i % 2
return f
[2022/10/6 : 2道]
【392. 判断子序列】
原题链接：https://leetcode.cn/problems/is-subsequence/
思路：
本题用动态规划的方法求解，和求最大公共子序列的长度问题类似，判断所求的最大公共子序列的长度是否等于给定字符串的长度，相等则可判断该字符串为另一个字符串的子序列。递推公式为： { d p [ i ] [ j ] = d p [ i ? 1 ] [ j ? 1 ] + 1 , s [ i ] = t [ j ] d p [ i ] [ j ] = m a x ( d p [ i ] [ j ? 1 ] , d p [ i ? 1 ] [ j ] ) , s [ i ] ≠ t [ j ] \begin{cases} dp[i][j] = dp[i - 1][j - 1] + 1, & s[i] =t[j] \\ dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]), & s[i] \neq t[j] \\ \end{cases} {dp[i][j]=dp[i?1][j?1]+1,dp[i][j]=max(dp[i][j?1],dp[i?1][j]),?s[i]=t[j]s[i]=t[j]?
代码：
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
slen = len(s)
tlen = len(t)
if slen > tlen:
return False
dp = [[0] * (tlen + 1) for _ in range(slen + 1)]
for i in range(1, slen + 1):
for j in range(1, tlen + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[slen][tlen] == slen
【746. 使用最小花费爬楼梯】
原题链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
思路：
首先初始化dp数组，dp[0] = dp[1] = 0，此后爬到第n阶的最小花费可以看作爬到第n-1阶花费加上n-1的费用与爬到第n-2阶花费加上n-2的费用的最小值，递推关系式为：
d p [ i ] = { 0 0 ≤ i ≤ 1 m i n ( d p [ i ? 1 ] + c o s t [ i ? 1 ] , d p [ i ? 2 ] + c o s t [ i ? 2 ] ) i ≥ 2 dp[i]= \begin{cases} 0 & 0\leq i \leq1 \\ min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]) & i \geq 2 \end{cases} dp[i]={0min(dp[i?1]+cost[i?1],dp[i?2]+cost[i?2])?0≤i≤1i≥2?
代码
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0 for _ in range(n + 1)]
dp[0] = dp[1] = 0
for i in range(2, n + 1):
dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])
return dp[n]
中等
[2022/10/6 : 2道]
【198. 打家劫舍】
原题链接：https://leetcode.cn/problems/house-robber/
思路：
声明一个二维数组 d p dp dp，维度为 ( n + 1 ) ? 2 (n+1) * 2 (n+1)?2，初始化数组元素为0。 i i i表示第 i i i个房子， d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示抢劫第 i i i个房子的总价值， d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示不抢劫第 i i i个房子的总价值。抢劫第 i i i个房子，则不能抢劫第 i ? 1 i-1 i?1个房子，再加上第 i i i个房子的价值。不抢劫第 i i i个房子，则总价值等于抢劫第 i ? 1 i-1 i?1个房子和不抢劫第 i ? 1 i-1 i?1个房子中的最大值。可以得到递推关系式为：
{ d p [ i ] [ 0 ] = d p [ i ] [ 1 ] = 0 i = 0 d p [ i ] [ 0 ] = d p [ i ? 1 ] [ 1 ] + n u m s [ i ? 1 ] , d p [ i ] [ 1 ] = m a x ( d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] ) 0 ≤ i ≤ n \begin{cases} dp[i][0] = dp[i][1] = 0 & i = 0 \\ dp[i][0] = dp[i - 1][1] + nums[i - 1], dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) & 0 \le i \leq n \end{cases} {dp[i][0]=dp[i][1]=0dp[i][0]=dp[i?1][1]+nums[i?1],dp[i][1]=max(dp[i?1][1],dp[i?1][0])?i=00≤i≤n?
代码
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0] * 2 for _ in range(n + 1)]
for i in range(1, n + 1):
# 0 rob and 1 not rob
dp[i][0] = dp[i - 1][1] + nums[i - 1]
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0])
return max(dp[n])
【213. 打家劫舍 II】
原题链接：https://leetcode.cn/problems/house-robber-ii/
思路:
与上一题的唯一区别是第 1 1 1个和第 n n n个房子不能同时打劫，所以可以算 [ 1 , n ? 1 ] [1,n-1] [1,n?1]的总价值和 [ 2 , n ] [2,n] [2,n]的总价值的最大值即可。
代码
# 法1
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp1 = [[0] * 2 for _ in range(n + 1)]
dp2 = [[0] * 2 for _ in range(n + 1)]
for i in range(1, n):
# 0 rob and 1 not rob
dp1[i][0] = dp1[i - 1][1] + nums[i - 1]
# 不偷第i个
dp1[i][1] = max(dp1[i - 1][1], dp1[i - 1][0])
v1 = max(dp1[n - 1])
for i in range(2, n + 1):
# 0 rob and 1 not rob
dp2[i][0] = dp2[i - 1][1] + nums[i - 1]
# 不偷第i个
dp2[i][1] = max(dp2[i - 1][1], dp2[i - 1][0])
v2 = max(dp2[n])
return max(v1, v2)
# 法2
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0 for _ in range(n + 1)]
dp[0] = 0
dp[1] = nums[0]
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
v1 = dp[n - 1]
dp[1] = 0
dp[2] = nums[1]
for i in range(3, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
v2 = dp[n]
return max(v1, v2)