原题链接
动态规划基本原理
动态规划（Dynamic Programming，简称 DP）是一种通过将原问题分解为相互重叠的子问题并只解决一次的方法来解决问题的算法优化技术。动态规划通常用于优化递归问题，通过存储子问题的解来避免重复计算，从而显著提高算法的效率。
基本思想
动态规划的基本思想是将原问题划分为若干个子问题，通过解决子问题得到原问题的解。在这个过程中，动态规划使用了最优子结构和重叠子问题两个关键性质。
-
最优子结构：问题的最优解可以通过子问题的最优解来构造。即，全局最优解包含了所有局部最优解。
-
重叠子问题：在递归求解过程中，对于一些子问题的解会被多次使用。为了避免重复计算，我们可以将子问题的解存储起来，后续直接使用，这就是动态规划中的记忆化。
基本步骤
动态规划通常包含以下基本步骤：
-
定义状态：明确定义问题的状态，找出问题中具有变化的量，并将其表示为状态。状态是原问题和子问题中变化的量。
-
找到状态转移方程：建立状态之间的关系，即如何由小的子问题推导出大问题的解。状态转移方程是动态规划的核心。
-
初始化：设置问题的初始值，通常是最简单的情况，这是递归或迭代的终止条件。
-
递推计算：按照状态转移方程，从初始状态开始递推计算，直到计算出原问题的解。
-
解决原问题：得到原问题的解，这通常是在状态中已经计算得到的值。
应用领域
动态规划广泛应用于各个领域，包括但不限于：
- 优化问题：如最短路径、最长子序列、背包问题等。
- 计算问题：如斐波那契数列、组合数等。
- 决策问题：如股票买卖、任务调度等。
总的来说，动态规划通过将复杂问题分解为简单的子问题，并有效地保存子问题的解，从而在时间和空间上实现了高效的问题求解。
找到最大开销的子字符串算法解析
问题描述
给定一个字符串 s，一个字符互不相同的字符串 chars 和一个长度与 chars 相同的整数数组 vals。子字符串的开销是一个子字符串中所有字符对应价值之和，空字符串的开销是 0。
字符的价值定义如下：
- 如果字符不在字符串
chars中，那么它的价值是它在字母表中的位置（下标从 1 开始）。 - 如果字符在
chars中的位置为i，那么它的价值就是vals[i]。
问题要求返回字符串 s 的所有子字符串中的最大开销。
思路
题目要求找到最大开销的子字符串，我们可以使用动态规划的思路解决。在这里，我们使用一个一维数组 dp 来记录以字符串 s 的每一位结尾的最大开销。
状态定义
我们定义 dp[i] 为以字符串 s 的第 i 位结尾的最大开销。
状态转移
状态转移方程为 dp[i] = max(dp[i - 1] + char_val, char_val)，其中 char_val 是第 i 个字符对应的开销值。
代码实现
class Solution:
def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
char_idx = {}
for idx, char in enumerate(chars):
char_idx[char] = idx
n = len(s)
dp = [0] * n
dp[0] = vals[char_idx[s[0]]] if s[0] in char_idx else ord(s[0]) - ord('a') + 1
ans = max(dp[0], 0)
for i in range(1, n):
new_char_val = vals[char_idx[s[i]]] if s[i] in char_idx else (ord(s[i]) - ord('a') + 1)
dp[i] = max(dp[i - 1] + new_char_val, new_char_val)
ans = max(ans, dp[i])
return ans
示例分析
示例 1
s = "adaa"
chars = "d"
vals = [-1000]
solution = Solution()
result = solution.maximumCostSubstring(s, chars, vals)
print(result) # Output: 2
解释：字符 “a” 和 “d” 的价值分别为 1 和 -1000。最大开销子字符串是 “aa”，它的开销为 1 + 1 = 2。2 是最大开销。
示例 2
s = "abc"
chars = "abc"
vals = [-1,-1,-1]
solution = Solution()
result = solution.maximumCostSubstring(s, chars, vals)
print(result) # Output: 0
解释：字符 “a”，“b” 和 “c” 的价值分别为 -1，-1 和 -1。最大开销子字符串是 “”，它的开销为 0。0 是最大开销。
复杂度分析
时间复杂度
遍历字符串 s 一次，每次更新 dp[i] 的操作为 O(1)，因此总时间复杂度为 O(n)。文章来源：https://www.toymoban.com/news/detail-773153.html
空间复杂度
使用了额外的空间来存储 dp 数组和 char_idx 字典，因此空间复杂度为 O(n)。文章来源地址https://www.toymoban.com/news/detail-773153.html
到了这里，关于【算法思考记录】动态规划入门！力扣2606. 找到最大开销的子字符串【Python3、动态规划】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
