动态规划基础问题 | 忆执惜来 = = 技能树点歪的尘尘

# 爬楼梯问题：

有一个楼梯，你每次可以爬 1 阶或 2 阶，问爬到第 n 阶有多少种不同的方法？

示例：

输入：n = 3
输出：3
解释：有三种方法可以爬到顶端：
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 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] + nums[i](\text{当前房子的价值})$
- 如果选择不偷，则一定是偷上一个房子 $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)$
确定初始状态和边界条件
- $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]

# 爬楼梯问题：

# 解题思路：

# 题目二：打家劫舍

# 解题思路：

# 题目三：最长递增子序列

# 解题思路：

# 编辑距离问题：

# 解题思路：

# 01 背包问题

# 解题思路：

# 最长回文子序列

# 解题思路

多层感知机器-多项式回归

C/Cpp数据结构+算法