Python动态规划实战：背包问题与最长公共子串详解

林舟

发布时间：2026-10-15| 5人浏览过

原创

本文深入解析Python中的动态规划技术，通过背包问题和最长公共子串两个经典案例，展示如何利用网格填充法解决最优化问题。文章详细阐述了状态转移逻辑，并提供完整的Python代码实现，帮助开发者掌握动态规划的核心思想与实战技巧。

背包问题

假设有一个最大承重为4个单位的背包，目标是装入物品后使总价值最大化。现有三件可选物品：物品A重量为1单位，价值15；物品B重量为3单位，价值20；物品C重量为4单位，价值30。

采用动态规划方法，通过构建网格逐步填充数据以寻找最优解。

class SolutionBag:
    def valuableBag(self,optionalList,sizeBig):
        #创建网格
        grid = [[0 for i in range(sizeBig+1)] for j in range(len(optionalList)+1)]
        #从行列序号1开始计数
        column = 1
        for v in optionalList.values():
            optionalWeight,optionalPrice = v
            for row in range(sizeBig):
                if optionalWeight > row+1:
                    grid[column][row+1] = grid[column-1][row+1]
                else:
                    grid[column][row+1] = max(grid[column-1][row+1],optionalPrice+grid[column-1][row+1-optionalWeight])
            column += 1
        return grid#SolutionBag().valuableBag({"A":(1,15),"B":(3,20),"C":(4,30)},4)

最长公共子串

在动态规划场景中，核心目标通常是最大化某个指标。例如，寻找两个字符串的最长公共子串。以单词“fish”和“fosh”为例，我们需要确定它们之间包含的最长公共子串是什么。

解决此问题的关键在于将其分解为子问题。我们不应直接比较完整的字符串如“hish”和“fish”，而是从较短的子串入手，先比较“his”和“fis”，通过子问题的解逐步构建最终结果。

具体实现上，我们利用网格填充策略来系统化地计算和存储中间状态。

#伪代码
#字母相同则左上方+1
if word1[i] == word2[j] :
    cell[i][j] = cell[i-1][j-1] +1
else:
    cell[i][j] = max(cell[i][j-1],cell[i-1][j])

以下是使用Python实现网格构建的具体代码示例。

class SolutionLengthS:
    def longestLength(self,str1,str2):
        grid = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]
        for i in range(len(str2)):
            for j in range(len(str1)):
                if str1[j] == str2[i] :
                    grid[i+1][j+1] = grid[i][j] + 1
                else:
                    grid[i+1][j+1] = max(grid[i+1][j],grid[i][j+1])
        return grid

至此，关于Python动态规划（涵盖背包问题和最长公共子串）的介绍已完成。如需了解更多相关Python动态规划内容，建议查阅本站历史文章或继续阅读后续章节，感谢大家的支持。