每日一算：动态规划算法

大家好，欢迎来到IT知识分享网。

《算法图解》：

需要在给定约束条件下优化某种指标时，动态规划很有用。

问题可分解为离散子问题时，可使用动态规划来解决。

每种动态规划解决方案都涉及网格。

单元格中的值通常就是你要优化的值。

每个单元格都是一个子问题，因此需要考虑将问题分解为子问题。

没有放之四海皆准的计算动态规划解决方案的公式。

个人理解，该算法的核心思想就将原问题拆解为多个子问题，解决问题的方法也是依赖于子问题的结果。

例如书中提到的，寻找两个字符串的最长公共子串问题，先看下面的代码，返回子串的长度。

def longestPublicStr(str1, str2): longest = 0 result = [[0 for i in range(len(str2))] for j in range(len(str1))] for i in range(len(str1)): for j in range(len(str2)): if str1[i] == str2[j]: if i == 0 or j == 0: result[i][j] = 1 else: result[j][i] = result[i-1][j-1] + 1 else: result[i][j] = 0 longest = max(longest, result[i][j]) return longest print(longest("histageh", "hibctageb"))

如果要返回的具体的子串可使用下面的代码：

def longestPublicStr(str1, str2): lstr = "" longest = 0 result = [[0 for i in range(len(str2))] for j in range(len(str1))] for i in range(len(str1)): for j in range(len(str2)): if str1[i] == str2[j]: if i == 0 or j == 0: result[i][j] = 1 else: result[j][i] = result[i-1][j-1] + 1 else: result[i][j] = 0 if longest < result[i][j]: longest = max(longest, result[i][j]) lstr = str1[i-longest+1:i+1] return lstr print(longest("histageh", "hibctageb"))

result[j][i] = result[i-1][j-1] + 1

上面这段代码可以理解为，后面的结果是建立在前面的子问题结果之上。

细节概念还需要多看看书中的详细介绍，这里只是根据书中的概念给自己出的一道题。