动态规划经典题目详解及答案

希赛网 2024-02-19 09:45:13

动态规划（Dynamic Programming, DP）是一种用来解决最优化问题的算法思想。自从20世纪50年代由Bellman提出以后，DP已经成为算法设计中一个非常重要的分支，在算法竞赛、数学等领域有着广泛的应用。在DP的学习中，许多经典的题目必不可少，下面就来详细解析几个常见的DP问题。

1. 爬楼梯问题

这是一个非常经典且简单的DP问题。题目描述：一个人在爬楼梯，每次可以向上走1阶或2阶，问到达n阶楼梯的不同方法数是多少。因为每次只能爬1阶或2阶，所以爬到第n阶楼梯的路径只有两种情况：从第n-1阶或从第n-2阶。那么到达第n阶楼梯的不同方法数就等于到达第n-1阶和到达第n-2阶的方法数之和。我们用f[i]表示到达第i阶楼梯的不同方法数，那么状态转移方程就可以写为：

f[i] = f[i-1] + f[i-2]

初始化：f[1]=1, f[2]=2

代码实现：

def climbStairs(n: int) -> int:

if n == 1:

return 1

if n == 2:

return 2

dp = [0] * (n + 1)

dp[1], dp[2] = 1, 2

for i in range(3, n + 1):

dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

2. 最长公共子序列问题

最长公共子序列（Longest Common Subsequence, LCS）问题是指给出两个序列，找出所有既在第一个序列中出现，又在第二个序列中出现的，且以相同顺序在两个序列中出现的所有字符串子序列，并返回其长度。比如字符串s1 = "bcdae"，s2 = "acdfae"的LCS为"cae"，长度为3。求LCS的问题可以通过动态规划解决。我们需要定义dp[i][j]表示字符串s1前i个字符和s2前j个字符的LCS长度。状态转移方程如下：

if s1[i-1] == s2[j-1]:

dp[i][j] = dp[i-1][j-1] + 1

else:

dp[i][j] = max(dp[i][j-1], dp[i-1][j])

初始化：dp[0][j] = dp[i][0] = 0，其中0<=i<=m, 0<=j<=n，m为s1的长度，n为s2的长度。

代码实现：

def longestCommonSubsequence(text1: str, text2: str) -> int:

m, n = len(text1), len(text2)

dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):

for j in range(1, n + 1):

if text1[i - 1] == text2[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[m][n]

3. 0/1背包问题

0/1背包问题是动态规划中最经典的问题之一。题目描述：给你n个物品和一个容量为C的背包，每个物品有重量w[i]和价值v[i]两个属性，问你如何选择装入背包的物品，使得装入背包的物品总重量不超过C，且价值最高。这个问题可以用DP来解决。我们可以定义dp[i][j]表示前i个物品在容量为j的背包中所能获得的最大价值。状态转移方程如下：

if j >= w[i]:

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

else:

dp[i][j] = dp[i-1][j]

初始化：dp[i][0]=dp[0][j]=0，其中0<=i<=n，0<=j<=C，n为物品数量。

代码实现：

def knapsack(W: int, N: int, weights: List[int], values: List[int]) -> int:

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):

for j in range(1, W + 1):

if j >= weights[i - 1]:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])