海外网站服务器租用_代驾小程序定制开发_杭州百度推广开户_太原整站优化排名外包

考虑用动态规划的情况
动态规划的时间复杂度
使用动态规划解决问题时需要关注
经典使用动态规划解决问题的案例
- 经典0-1背包问题
- 最长公共子序列
- 最长连续子序列
- 最长递增子序列
- 最长连续递增子序列
- 回文子串的数量
- 最长的回文子串

考虑用动态规划的情况

一个问题如果具有重叠子问题和最优子结构特征，那么初步考虑可以使用动态规划。
重叠子问题：在递归求解过程中，相同的子问题被多次计算。
最优子结构：问题的最优解可以由其子问题的最优解组合而成。

动态规划的时间复杂度

动态规划的时间复杂度通常取决于状态的数量和状态转移的复杂度。

使用动态规划解决问题时需要关注

状态定义：dp数组的含义。
状态转移方程：既然最优解会依赖于子问题的最优解，那么具体是怎么依赖的。
初始化：确定动态规划表的初始值。这通常取决于问题的具体情况，例如，对于最长递增子序列问题，每个元素的初始值为1，因为每个元素本身可以看作一个长度为1的递增子序列。
边界条件：确定问题的边界条件，即在哪些情况下可以直接得出结果，不需要进一步的计算。例如，在0-1背包问题中，如果背包容量为0，或者物品数量为0，那么最大价值显然为0。
遍历顺序：确定遍历的顺序，以保证在计算某个状态时，其依赖的所有状态都已经被计算。例如，在0-1背包问题中，通常先遍历物品，再遍历背包容量；而在最长递增子序列问题中，通常从左到右遍历序列。
时间复杂度：很多时候使用动态规划解决问题时，是方便了理解解决思路，但是不一定时间复杂度就也很低。

经典使用动态规划解决问题的案例

经典0-1背包问题

问题描述：给定一组物品，每个物品有对应的价值和重量。同时给定一个背包，背包的最大承重能力为capacity。目标是在不超过背包容量的前提下，选择物品放入背包，使得背包中物品的总价值最大化。
状态定义：dp[i][j]表示考虑前i个物品，在容量为j的背包下能获得的最大价值。
状态转移方程：
- 如果不选择第i个物品：dp[i][j] = dp[i-1][j]
- 如果选择第i个物品：dp[i][j] = dp[i-1][j - w[i]] + v[i]（前提是j >= w[i]）
时间复杂度：O(n * W)，其中n是物品数量，W是背包容量。

代码实现：

def knapsack(values, weights, capacity):"""0-1背包问题:param values: 物品的价值列表:param weights: 物品的重量列表:param capacity: 背包的最大容量:return: 最大价值"""n = len(values)# 初始化动态规划表，dp[i][j]表示前i个物品在容量为j时的最大价值dp = [[0] * (capacity + 1) for _ in range(n + 1)]# 状态转移for i in range(1, n + 1):  # 遍历每个物品for j in range(1, capacity + 1):  # 遍历每个容量if weights[i - 1] <= j:  # 如果当前物品可以放入背包# 选择放入或不放入的最大价值dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])else:# 当前物品无法放入背包，继承上一个物品的状态dp[i][j] = dp[i - 1][j]# 返回最大价值return dp[n][capacity]# 示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(knapsack(values, weights, capacity))  # 输出：220

最长公共子序列

问题描述：给定两个字符串seq1和seq2，目标是找到它们的最长公共子序列的长度。公共子序列是指在两个字符串中都出现的子序列，但不要求这些字符在原字符串中是连续的。
状态定义：dp[i][j]表示第一个序列的前i个字符和第二个序列的前j个字符的最长公共子序列的长度。
状态转移方程：
- 如果seq1[i-1] == seq2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
时间复杂度：O(m * n)，其中m和n分别是两个序列的长度。

代码实现：

def longest_common_subsequence(seq1, seq2):"""最长公共子序列:param seq1: 第一个序列:param seq2: 第二个序列:return: 最长公共子序列的长度"""m, n = len(seq1), len(seq2)# 初始化动态规划表，dp[i][j]表示seq1的前i个字符和seq2的前j个字符的最长公共子序列的长度dp = [[0] * (n + 1) for _ in range(m + 1)]# 状态转移for i in range(1, m + 1):for j in range(1, n + 1):if seq1[i - 1] == seq2[j - 1]:  # 如果当前字符相同dp[i][j] = dp[i - 1][j - 1] + 1else:# 如果当前字符不同，取两种情况的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])# 返回最长公共子序列的长度return dp[m][n]# 示例
seq1 = "ABCBDAB"
seq2 = "BDCABC"
print(longest_common_subsequence(seq1, seq2))  # 输出：4

最长连续子序列

问题描述：给定一个整数序列nums，目标是找到其中最长的连续子序列的长度。这里的“连续”指的是数值上的连续，例如[1, 2, 3, 4]是一个长度为4的连续子序列。
状态定义：dp[i]表示以第i个元素结尾的最长连续子序列的长度。
状态转移方程：
- 如果nums[i] == nums[i-1] + 1，则dp[i] = dp[i-1] + 1
- 否则，dp[i] = 1
时间复杂度：O(n)，其中n是序列长度。

代码实现：

def longest_consecutive_subsequence(nums):"""最长连续子序列:param nums: 数字序列:return: 最长连续子序列的长度"""if not nums:return 0# 对数组排序nums.sort()n = len(nums)# 初始化动态规划数组，dp[i]表示以第i个元素结尾的最长连续子序列的长度dp = [1] * n# 状态转移for i in range(1, n):if nums[i] == nums[i - 1] + 1:  # 如果当前元素与前一个元素连续dp[i] = dp[i - 1] + 1# 返回最长连续子序列的长度return max(dp)# 示例
nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive_subsequence(nums))  # 输出：4

最长递增子序列

问题描述：给定一个整数序列nums，目标是找到其中最长的递增子序列的长度。递增子序列是指子序列中的元素是严格递增的，但不要求这些元素在原序列中是连续的。
状态定义：dp[i]表示以第i个元素结尾的最长递增子序列的长度。
状态转移方程：
- 对于每个j < i，如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j] + 1)
时间复杂度：O(n^2)，其中n是序列长度。如果使用二分查找优化，时间复杂度可以降低到O(n log n)。

代码实现：

def longest_increasing_subsequence(nums):"""最长递增子序列:param nums: 数字序列:return: 最长递增子序列的长度"""if not nums:return 0n = len(nums)# 初始化动态规划数组，dp[i]表示以第i个元素结尾的最长递增子序列的长度dp = [1] * n# 状态转移for i in range(1, n):for j in range(i):if nums[i] > nums[j]:  # 如果当前元素大于前一个元素dp[i] = max(dp[i], dp[j] + 1)# 返回最长递增子序列的长度return max(dp)# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longest_increasing_subsequence(nums))  # 输出：4

最长连续递增子序列

问题描述：给定一个整数序列nums，目标是找到其中最长的连续递增子序列的长度。这里的“连续”指的是数值上的连续，且子序列中的元素在原序列中也是连续的。
状态定义：dp[i] 表示以第i个元素结尾的最长连续递增子序列的长度。
状态转移方程：
- 如果nums[i] > nums[i-1]，则dp[i] = dp[i-1] + 1。
- 否则，dp[i] = 1（即从当前元素重新开始一个新的连续递增子序列）。
时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组即可完成状态转移。

代码实现：

def longest_continuous_increasing_subsequence(nums):"""最长连续递增子序列:param nums: 数字序列:return: 最长连续递增子序列的长度"""if not nums:return 0n = len(nums)# 初始化动态规划数组，dp[i]表示以第i个元素结尾的最长连续递增子序列的长度dp = [1] * n# 状态转移for i in range(1, n):if nums[i] > nums[i - 1]:  # 如果当前元素大于前一个元素dp[i] = dp[i - 1] + 1  # 当前子序列长度加1else:dp[i] = 1  # 否则重新开始一个新的连续递增子序列# 返回最长连续递增子序列的长度return max(dp)# 示例
nums = [1, 3, 5, 4, 7]
print(longest_continuous_increasing_subsequence(nums))  # 输出：3nums = [2, 2, 2, 2, 2]
print(longest_continuous_increasing_subsequence(nums))  # 输出：1

回文子串的数量

问题描述：给定一个字符串s，目标是统计其中回文子串的数量。回文子串是指正读和反读都相同的子串。
状态定义：dp[i][j]：布尔值，表示子串s[i..j]是否是回文。
状态转移方程：
- 当s[i] == s[j]：如果j - i <= 1，即子串长度为1或2，直接判断为回文。
- 当s[i] == s[j]：如果j - i > 1，则需要检查dp[i + 1][j - 1]是否为回文。
时间复杂度：O(n²)，其中n是字符串的长度。

代码实现：

def countSubstrings(s):n = len(s)if n == 0:return 0# 初始化动态规划表dp = [[False] * n for _ in range(n)]count = 0# 单个字符一定是回文for i in range(n):dp[i][i] = Truecount += 1# 检查长度为2的子串for i in range(n - 1):if s[i] == s[i + 1]:dp[i][i + 1] = Truecount += 1# 检查长度大于2的子串for length in range(3, n + 1):  # 当前子串长度for i in range(n - length + 1):  # 子串起始位置j = i + length - 1  # 子串结束位置if s[i] == s[j] and dp[i + 1][j - 1]:dp[i][j] = Truecount += 1return count# 示例
s = "abc"
print(countSubstrings(s))  # 输出：3s = "aaa"
print(countSubstrings(s))  # 输出：6

最长的回文子串

问题描述：给定一个字符串s，目标是找到其中最长的回文子串。回文是指正读和反读相同的字符串。
状态定义：dp[i][j]：布尔值，表示子串s[i..j]是否是回文。
状态转移方程：
- 如果s[i] == s[j]，且dp[i+1][j-1]为True，则dp[i][j] = True。
- 否则，dp[i][j] = False。
时间复杂度：O(n²)，其中n是字符串的长度。

代码实现：

def longestPalindrome_dp(s):n = len(s)if n < 2:return s# 初始化动态规划表dp = [[False] * n for _ in range(n)]start, max_len = 0, 1# 单个字符一定是回文for i in range(n):dp[i][i] = True# 检查长度为2的子串for i in range(n - 1):if s[i] == s[i + 1]:dp[i][i + 1] = Truestart = imax_len = 2# 检查长度大于2的子串for length in range(3, n + 1):  # 当前子串长度for i in range(n - length + 1):  # 子串起始位置j = i + length - 1  # 子串结束位置if s[i] == s[j] and dp[i + 1][j - 1]:dp[i][j] = Truestart = imax_len = lengthreturn s[start:start + max_len]# 示例
s = "babad"
print(longestPalindrome_dp(s))  # 输出："bab" 或 "aba"