动态规划作为算法的必考内容,重要性不言自明。如何理解动态规划,并能够应用到实际场景中,这是本节的重点。
一、动态规划
动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。
但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用。
二、解决方案
1.每种动态规划解决方案都涉及网格。
2.单元格中的值通常就是你要优化的值。在前面的背包问题中,单元格的值为商品的价值。
3.每个单元格都是一个子问题,因此你应考虑如何将问题分成子问题,这有助于你找出网格的坐标轴。
三、最长公共子序列之解决方案
我们来看看网格法求 FORT
和 FOSH
,首先绘制如下网格:
具体的思路如下:
按照上面的分析,核心代码片段可能如下:
1 2 3 4
|
if word_a[i] == word_b[j]: ←--------两个字母相同 cell[i][j] = cell[i-1][j-1] + 1 else: ←------------------------------两个字母不同 cell[i][j] = max(cell[i-1][j], cell[i][j-1])
|
四、最长公共子串
如上图,核心代码片段可能如下:
1 2 3 4
|
if word_a[i] == word_b[j]: ←---------两个字母相同 cell[i][j] = cell[i-1][j-1] + 1 else: ←------------------------------两个字母不同 cell[i][j] = 0
|
五、实际应用
编写一个函数来查找字符串数组中的最长公共前缀。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
var longestCommonPrefix = function(strs) { if(strs.length === 0) return ''; let result = ''; let len = Math.min.apply(Math, strs.map(item => item.length)); for(let i = 0; i < len; i++) { let tmp = strs.map(item => item.substring(0, i+1)); if (new Set(tmp).size === 1) result = tmp[0]; } return result; };
|
六、学习目录