字符串拆分最低成本问题：递归转Dynamic Programming实现相关疑问

1. DP表设计疑问解答 #

你不需要构造二维DP表，仅需使用一维DP数组即可实现需求：
我们定义dp[i]为拆分字符串前i个字符的最低总成本，i的取值范围是0 ~ len(sentence)，其中dp[0]对应空串的拆分成本，作为初始边界值。你原先设想的二维表方案属于过度设计，完全不需要按子串设置行维度。

2. 状态转移逻辑解答 #

状态转移的逻辑完全对齐你已实现的递归逻辑：

• 初始状态：dp[0] = 0（空串不需要拆分，成本为0），其余dp[i]初始化为无穷大（代表初始状态下该长度的字符串不可拆分）
• 对于每个位置i（从1遍历到字符串总长度），遍历cost_list中所有子串条目：
  • 取当前子串的长度k，成本c
  • 当i >= k，且sentence[i-k:i]和当前子串完全相等时，就可以用前i-k个字符的最低成本加上当前子串的成本，更新当前dp[i]的最小值：dp[i] = min(dp[i], dp[i-k] + c)
• 最终dp[len(sentence)]就是整个字符串的最低拆分成本。

完整DP实现代码 #

def find_lowest_cost(sentence, cost_list):
    n = len(sentence)
    # dp[i] 表示前i个字符的最小拆分成本
    dp = [float('inf')] * (n + 1)
    dp[0] = 0  # 空串成本为0
    for i in range(1, n+1):
        for substr, cost in cost_list:
            k = len(substr)
            if i >= k and sentence[i-k:i] == substr:
                dp[i] = min(dp[i], dp[i - k] + cost)
    return dp[n]

# 测试用例
sentence = "xxxyyzz"
cost_list = [["x", 1], ["xx", 3], ["y", 3], ["yy", 1], ["z", 2]]
print(find_lowest_cost(sentence, cost_list)) # 输出为8，和预期结果一致

内容的提问来源于stack exchange，提问作者Kevin Lu