动态规划经典问题实战解析与Python实现
本文深入解析了爬楼梯、打家劫舍、最长递增子序列、编辑距离、01背包和最长回文子序列等多个动态规划经典问题，详细阐述解题思路及Python代码实现，助你掌握DP核心思想。
- 算法
爬楼梯问题：
有一个楼梯，你每次可以爬1阶或2阶，问爬到第n阶有多少种不同的方法？
示例：
- 输入：n = 3
- 输出：3
- 解释：有三种方法可以爬到顶端：
- 1阶 + 1阶 + 1阶
- 1阶 + 2阶
- 2阶 + 1阶
解题思路：
- 确定状态和状态变量
- 明确问题状态是什么
- 用什么变量表示问题的状态
- 问题是爬到第n阶有多少种不同的方法，那么状态可以是当前的台阶数，可以用变量n表示
- 确定状态转移公式
- 即当前状态与之前状态的关系
- 针对爬楼梯的问题,$dp[i]$表示台阶数为i的方法数，根据题目条件$dp[i] = dp[i - 1]\text{爬一阶} + dp[i - 2]\text{爬两阶}$，所以这里就是你要求爬n阶有几种方法那就是求到$n-1$阶和到$n-2$阶有几种方法。同理，可以往前推。
- 确定边界条件和初始值
- 一般就是什么都没做之前的初始状态
- 比如，一开始没有台阶$dp[0] = 0$，登上第一个台阶$dp[1] = 1$， 登上第二个台阶$dp[2] = 2$
- 确定计算顺序
- 通常是自底向上或者自顶向下(递归+记忆化)
- 自底向上：先计算小规模问题的解，再由此计算大规模问题的解
- 自顶向下：从大问题开始，递归求解小问题，并记录已解决的子问题结果
- 空间优化（可选）：
- 检测是否可以优化空间，比如求解之后的状态或许只需要前面几个的状态不需要前面全部状态
n = int(input())
m = [0] * (n + 1)
m[1] = 1
m[2] = 2
for i in range(3, n + 1):
m[i] = m[i - 1] + m[i - 2]
print(m[n])题目二：打家劫舍
一条街上有n个房子，每个房子里有一定价值的财宝。如果你偷了相邻的两个房子，就会触发警报。求在不触发警报的情况下，你能偷到的最大价值。
示例：
- 输入：[1, 2, 3, 1]
- 输出：4
- 解释：偷第1个房子（值=1）和第3个房子（值=3）
解题思路：
- 寻找状态变量：
- 问题是能偷到的最大价值，那么可以设置偷到第$i$个房子的最大价值，直到算到第n个房子。$dp[i]$代表偷到第i个房子的最大价值
- 寻找递推关系：
- 判断第$i$个房子是否偷或者不偷，如果选择偷,那么就是前一个房子不偷的情况去偷当前这个房子$dp[i] = dp[i-2] + numsi$
- 如果选择不偷，则一定是偷上一个房子$dp[i] = dp[i - 1]$
- 所以我们取最大值
- 设置初始值和边界条件
- $dp[0] = 0,dp[1] = max(nums[0],nums[1])$
- 确定顺序
- 自下向上
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
nums = list(map(int, input().split()))
print(rob(nums))题目三：最长递增子序列
给你一个整数数组，找出其中最长严格递增子序列的长度。
示例：
- 输入：[10, 9, 2, 5, 3, 7, 101, 18]
- 输出：4
- 解释：最长递增子序列是 [2, 3, 7, 101]，长度为4
解题思路：
- 确定状态以及状态变量
- 题目要求找出最长严格递增子序列的长度，那么子序列的长度是我们要求的值，我们当前的状态可以是遍历到第i个字符得到的最长递增子序列的长度，dp[i]代表序列长度
- 寻找递推关系
- 判断到第i个字符时，如果他比之前第$j(j<i)$个字符大那么他的最长序列长度，就是$第j个字符的最长序列长度 + 1$，由于j有$i-1$个选择，我们取其中的最大值，即$dp[i] = max(dp[i],dp[j] + 1)$
- 最终我们返回所有字符最长序列的最大值
- 确定初始状态和边界条件
- 每个字符的长度都是$1$，所以$dp[i]$最初为$1$
- 确定计算顺序
- 由下向上
def sub_sequence(nums):
max_len = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
max_len[i] = max(max_len[i], max_len[j] + 1) # 这里一定是与max_len[i]做比较 max_len[i]在第二次循环是会变的 ，我们要找的是变化过程的最大值
return max(max_len)
nums = list(map(int, input().split()))
print(sub_sequence(nums))编辑距离问题：
给你两个单词 word1 和 word2，需要计算将 word1 转换成 word2 所使用的最少操作数。可以进行三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
解题思路：
- 确定状态变量：
- 问题是将word1转换成word2 ，那么可以找word1的前$i$个字符转换到word2的前$j$个字符的最少操作数字。
- $dp[i][j]$代表word1的前i个字符转换成word2的前j个字符的最少操作数
- 寻找递推关系
- 我们有三种操作方式，针对每一种操作方式，都需要不同的计算。比如（注意 这里的i，j不一定相同哦 hor 变到 s 也是通过这三种操作可以的，所以我们需要双重遍历）：
- 选择插入操作：是在$word1$的第i个字符和第j个字符不相同且$word1$的前$i$个字符匹配$word2$的前$j-1$个字符的情况下才会选择插入操作。此时$dp[i][j] = dp[i][j-1] + 1$
- 选择删除操作：是在word1的第i个字符和第j个字符不相同且word1的前i-1个字符通过一定的操作数匹配到word2的前j个字符的情况下才会选择删除第i个字符。此时$dp[i][j] = dp[i-1][j] + 1$
- 选择替换操作：是在$word1$的第$i$个字符和第$j$个字符不相同且$word1$的前$i-1$通过一定的操作数匹配到$word2$的前$j - 1$个字符的情况下选择替换第i个字符。此时$dp[i][j] = dp[i-1][j-1] + 1$
- 不进行操作: 在$word1$的第$i$个字符和$word2$的第$j$个字符相同的时候，我们无需进行任何操作。此时$dp[i][j] = dp[i-1][j-1]$
- 最终我们取最小值$dp[i][j] = min(dp[i][j] = dp[i][j-1] + 1,dp[i][j] = dp[i-1][j] + 1,dp[i][j] = dp[i-1][j-1] + 1)$
- 我们有三种操作方式，针对每一种操作方式，都需要不同的计算。比如（注意 这里的i，j不一定相同哦 hor 变到 s 也是通过这三种操作可以的，所以我们需要双重遍历）：
- 确定初始状态和边界条件
- $dp[0][0] = 0$
- 如果$word1$为空字符串，$dp[0][j] = j$
- 如果word2为空字符串，$dp[i][j] = i$
- 确定计算顺序
- 由下向上
def minDistnce(word1,word2):
m = len(word1)
n = len(word2)
dp = [[0 for i in range(n+1)] for j in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i==0 or j==0:
dp[i][j] = 0
# 我们需要判断第i个字符和第j个字符是否相等
elif word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
# 分别执行的是替换，删除，插入
dp[i][j] = min(dp[i-1][j-1] + 1,dp[i-1][j] + 1,dp[i][j-1] + 1)
return dp[m][n]
word1 = "horse"
word2 = "ros"
print(minDistnce(word1,word2))01背包问题
有n个物品，每个物品有一个重量w和一个价值v。现在你有一个容量为W的背包，问你如何选择物品放入背包，使得背包内物品的总价值最大？
示例：
- 物品：[(重量=2, 价值=3), (重量=1, 价值=2), (重量=3, 价值=4)]
- 背包容量：W = 4
- 输出：6
- 解释：选择第1个和第2个物品，总重量=3，总价值=5
解题思路：
- 确定状态和状态变量：
- 一个容量为W的背包，如何选择物品放入背包使得背包的物品总价值最大？问题涉及到两个东西一个是$背包$一个是$物品$，那么我们可以确定两个状态 一个是第i个物品，另一个是当前背包的重量j，则$dp[i][j]$表示取第i个物品的时候，背包重量为j的情况下所达到的最大价值。
- 寻找递推关系：
- 针对每个物品我们都可以选择拿与不拿。
- 如果选择拿，我们需要判断j是否比$w_i$大，如果大才可以拿否则不能。如果能拿$dp[i][j] = dp[i-1][j-w_i] + v_i$
- 如果不能拿或者选择不拿那么$dp[i][j] = dp[i-1][j]$
- 针对这两种情况 我们取最大值$dp[i][j] = max(dp[i-1][j-w_i] + v_i,dp[i-1][j])$
- 确定初始状态和边界条件
- 一开始没有拿物品$dp[0][0] = 0$
- 确定计算顺序
- 从下向上
# 背包问题
def bag(items,capacity):
n = len(items)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
weight,value = items[i-1]
for j in range(1, capacity + 1):
if weight <= j:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight] + value)
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity] # 返回最终状态的值
# 读取物品数量和背包容量
n,capacity = map(int,input().split())
items = []
for i in range(n):
weight,value = map(int,input().split())
items.append((weight,value))
result = bag(items, capacity)
print(result)最长回文子序列
给定一个字符串 s，找到其中最长的回文子序列的长度。
回文子序列是指在不改变剩余字符顺序的情况下，可以通过删除某些字符（或不删除）得到的序列，例如，“bbab” 的子序列有 “bbb”，“bab” 等等，其中 “bab” 是最长的回文子序列。
示例：
- 输入: “bbbab”
- 输出: 4
- 解释: 一个可能的最长回文子序列为 “bbbb”，另一个可能的为”baba”。
解题思路
- 确定状态变量
- 问题是返回最长的回文子序列的长度，我们可以使用i表示回文字符串开始的位置，使用j表示回文字符串结束的位置，则$dp[i][j]$表示判断索引i到j的字符串时最大的回文序列长度。
- 寻找递推关系
- 我们可以判断第i个字符是否等于第j个字符
- 两者相等，那么最大回文序列长度就是不包含他两的最大长度 + 2,也就是他们可以被同时纳入回文序列长度，即$dp[i][j] = dp[i+1][j-1] + 2$
- 两者不想等，则最大回文序列是包含他们其中一个的最大回文序列长度，不能被同时纳入回文序列长度，$dp[i][j] = max(dp[i][j-1],dp[i+1][j])$
- 确定初始状态
- 每个字符的回文序列都应该是1，即$dp[i][i] = 1$
- 确定计算顺序
- 由下向上
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
# 初始化长度为1的回文
for i in range(n):
dp[i][i] = 1
# 计算长度为2，3。。。的回文
for length in range(2,n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][n-1]
留言讨论
0 条留言
正在加载留言...