动态规划python代码

以下是一个简单的动态规划Python代码示例，用于解决最长公共子序列问题：

def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[None]*(n+1) for i in range(m+1)]

for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])

return L[m][n]

X = "AGGTAB"
Y = "GXTXAYB"

print("Length of LCS is ", lcs(X, Y))

输出：Length of LCS is 4

该代码使用二维数组来存储子问题的解，并使用两个嵌套循环来填充数组。在填充数组之前，代码首先创建一个空数组，然后将第一行和第一列初始化为0。接下来，代码通过比较两个字符串中的字符来填充数组。如果字符相同，则将左上角单元格的值加1。否则，代码将左上角单元格的最大值复制到当前单元格。最后，代码返回右下角单元格的值，该值是最长公共子序列的长度。

相关问题

动态规划python代码模板

动态规划是一种常用的算法思想，可以用来解决一些具有重叠子问题性质的问题。下面是一个动态规划的Python代码模板：

def dynamic_programming_template(target, ways):
    dp = [0] * (target + 1)
    dp[0] = 1

    for i in range(1, target + 1):
        for j in range(len(ways)):
            if ways[j] <= i:
                dp[i] += dp[i - ways[j]]

    return dp[target]

这个模板中，`target`表示目标值，`ways`表示可选的方式列表。模板使用一个`dp`数组来保存中间结果，`dp[i]`表示达到目标值`i`的方法数。通过遍历`ways`列表，对于每个`i`，计算`dp[i]`的值。最后返回`dp[target]`即可得到结果。

0/1背包问题 动态规划 python代码

很高兴为您提供答案！关于0/1背包问题的动态规划Python代码，以下是一个标准的示例代码：

def knapSack(W, wt, val, n):
 
    if n == 0 or W == 0 :
        return 0
 
    if (wt[n-1] > W):
        return knapSack(W, wt, val, n-1)  
  
    else:
        return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                   knapSack(W, wt, val, n-1))
           
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

这段代码就是实现了0/1背包问题的动态规划求解。其中，val数组存放了每个物品的价值，wt数组存放了每个物品的重量，W表示背包的最大承重，n表示物品的数量。运行上述代码，输出的结果是220，即背包能够承载的最大价值是220。

希望这能够帮助到您，有任何其他问题，欢迎随时向我提出！