一个小例子

问 : 1+1+1+1+1 = ？

答 ：5

问：再 + 1 = ?

答 ：6

这就是DP算法的大概意思，比起问6个1相加等于6，需要计算6次。那么把之前计算过的5个1相加等于5再加上1等于6，这样拿到结果少计算了5次。把1+1换成复杂的运算，基本就适用于各种DP算法的场景了。

DP算法

通过把复杂的问题，分解成较简单的子问题合集，再把子问题的结果保存在一般是带索引的数据结构里。下次再需要计算的时候则把已经计算完的值拿来用以缩短计算时间。

CodeWars 问题 Sums of Parts

首先举个简单的例子，在解决这个问题的时候甚至很难察觉到使用到了DP算法

Let us consider this example (array written in general format): （举个例子，如下方数组）

<code>ls = [0, 1, 3, 6, 10]/<code>

Its following parts:（如下）

<code>ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []/<code>

The corresponding sums are (put together in a list)（对应输出结果放在一个数组里应该是）:

<code> [20, 20, 19, 16, 10, 0]/<code>

如果直接按照逻辑来写的话，代码应该是，先计算出每个shift完的数组，求和，再合并。有点麻烦。

<code>//不自觉的一写就是这样，本质上就是DP算法了，因为最后要求的结果数组中，每一项都是可以基于下一项来计算出
function partsSums(ls) {
    let dp = Array(ls.length+1).fill(0)
    let count = 0
    ls.reduceRight((total,ele)=>{return dp[++count]=total+ele},0)
    return dp.reverse()
}
//准确的说，这个问题 ， 并不是用DP算法解决问题，而是在解决问题的过程中，实现了DP算法的思路。
//最后返回的结果 dp 其实就是大部分DP算法的中间寄存的数据结构。/<code>

热身结束。我们接下来用3个问题循序渐进的的研究下 Dynamic Programming

1 ，Maximum SubArray 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

<code>输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。/<code> 

第一步 ：确定 dp 数组 的值 应该是 以 dp 数组的索引 i 为终点的 最大子序和

<code>let dp = Array(inputArray.length) // dp[i] 的值就是 以i为终点 的 最大子序和/<code>

第二步 : 确定逻辑，dp[i]的值应该用什么逻辑来计算？

<code>dp[i] = Math.max( inputArray[i] , dp[i-1]+inputArray[i] ) 
//这里需要注意，先不考虑 dp[i-1] 是怎么计算 出来就是 它的最大子序和的
//只考虑 已知dp[i-1]就是最大子序和，那么要计算dp[i]的最大子序和需要什么样的逻辑。
//最大子序 是连续的 所以 对于 dp[i]来说，就是带不带 inputArray[i] 加入的问题，带就加上，不带就重新开始/<code>

第三步 : 敲代码 ^_^

<code>function maxSubArray (nums) {
  let dp = new Int32Array(nums.length+1)
  nums.map((e,i)=>{
  \tdp[i+1] = Math.max(nums[i],dp[i]+nums[i])
  })
  dp[0] = nums[0] //本来想直接 dp.shift() 。没想到typedArray不支持这个方法
\treturn Math.max(...dp)
}
//程序有点瑕疵，在没有shift掉的情况下，dp[i]表示的其实是 nums[i-1]的 maxSubArrayLength
//用 map 又不写判断的问题，还是 for 循环更合适，算了，绕一点连连脑吧。跟理解DP算法比不算什么
//把最后的比较放在map里 那就是 一次遍历 复杂度是 O(N) , 空间上还有优化空间 ^_^/<code> 

2，LIS Longest Increasing Subsequence 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

<code>输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。/<code>

第一步，确定dp数组 要存储的 内容 ，dp[i]应该是 把inputArray[i]作为数组的结尾，存储最长上升子序列的长度。（有了问题1的铺垫这里无需赘述了。逻辑相同）

第二步，确定逻辑，dp[i]的值相比于dp[i-1]应该如何去计算

<code>dp[i] = inputArray[i] > inputArray[i-1] ? dp[i-1] + 1 : dp[i]
//如果 inputArray[i] 比 上一个要大的 话 ，那么“最长”上升子序列的长度就应该+1，否则不变
//上方的想法是错误的。对于[1,2,0,3]这种情况 2对应的dp[i]应该是2，那么0对应的dp[i]也是2,明显是错误的
//也就是说
dp[i] = inputArray[i] > inputArray[j] ? dp[j]+1 : dp[i] // j的范围是 0 -> i-1
//同时还要保证dp[i]在经历了一轮循环后一直保持在最大值
//比如这种情况[1,2,3,0,1]
dp[i] = inputArray[i] > inputArray[j] ? Math.max( dp[j]+1 , dp[i] ): dp[i]/<code>

第三步 ，来了老弟

<code>function lengthOfLIS (nums) { 

\tlet size = nums.length
  let dp = new Int32Array(size).fill(1)
  for( let i = 1 ; i < size ; i++ ){
  \tfor(let j = 0 ; j < i ; j++){
    \tdp[i] = nums[i] > nums[j] ? Math.max( dp[j]+1 , dp[i] ): dp[i]
    }
  }
  return Math.max(...dp)
}
//在解题的过程中会感觉到 第二层 循环有可以优化的地方。mark一下 由于是两个循环复杂度是 O(N²)/<code>

强迫症，优化一下吧

第二层循环其实没有必要从0开始，从第一个最大dp[j]开始就可以了，比这个位置j更小的值就算再+1，最后的最大值顶多相等。

<code>function lengthOfLIS (nums) {
\tlet size = nums.length
    if(size===0)return 0 //增加一个空数组的判断
    let dp = new Int32Array(size).fill(1)
    let biggest = 1 // 新增一个最大值 也就是 dp[i]最大的那个的存储位置
    let bIndex = 0 // 索引位置，
    for( let i = 1 ; i < size ; i++ ){
  \t    for(let j = bIndex ; j < i ; j++){
    \t    dp[i] = nums[i] > nums[j] ? Math.max( dp[j]+1 , dp[i] ): dp[i]
        }
      //更新 biggest的值用于比较 更新bIndex的位置
        if(dp[i]>biggest){
            bIndex = i-1 ;
            biggest = dp[i]
        }
    }
    return biggest
}
//这样来看，计算量少了一半，第二个循环那里应该还是可以继续优化了。/<code> 

3，LCS Longest Common SubSequence 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。

<code>输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。/<code>

第一步，确定dp数组，之前的输入都是单数组，这回是两个字符串，也就当成两个数组吧。不管dp的结构如何，dp的每一项含义是确定的，在当前情况下，代表两个字符串的最长公共子序列。

<code>我们拿 text1 = "abc", text2 = "cde" 举个例子
dp的结构如果是
\\ a b c |
a 0 
c
---------/<code>

我们确定dp的结构是二维数组，没一项代表当前情况下的 两个裁剪后的字符串的最长公共子序列

第二步，确定逻辑 , 在两个值相等的情况下，右下角的值由对应的左上位置+1,反之，取两个边的最大值。这里要研究一遍二维数组的规律。发现存在这样的逻辑。

<code>dp[i][j] = text1[i] === text2[j] 
  ? dp[i-1][j-1] + 1 
\t: Math.max(dp[i-1][j],dp[i][j-1])
//要注意 现在的 i j 都只是我们自己理解的循环中的结构。逻辑上还不严谨/<code>

第三步，动手

<code>var longestCommonSubsequence = function(text1, text2) {
    let [l1,l2] = [text1.length,text2.length]
    let dp = Array.from(text1+' ',()=>new Int32Array(l2+1))
    for(let i = 1 ; i<=l1 ; i++){
        for(let j = 1 ; j <= l2 ; j++){
\t\t\t\t\tdp[i][j] = text1[i-1] === text2[j-1] 
            ? dp[i-1][j-1] + 1Math.max(dp[i-1][j],dp[i][j-1])
        }
    }
    return dp[l1][l2]
};/<code>

总结

如果第一次接触 dynamic programming 不要急 ， 这东西还是要多想的。它非常适用于“子结构”的计算。如果遇到各种各样的 子结构 并且结构复杂，不妨试试 DP算法。

这回的 代码里 Array.from 是个较新的尝试 ，Array.prototype.reduceRight , Math.max，跟之前相关，现在使用上已经很熟练了。 Array.prototype.fill 填补了 js数组里初始化比较尴尬的情况 。typedArray 比如 Int32Array这次就来试一试，在原型方法上跟Array还是有差距了，比如shift就不行，原因自然就是已经分配好了一段buffer空间了吧。[a,b] = [b,a] 解构赋值 了解下 ？

閱讀更多 野碼無繮 的文章

關鍵字: 数据结构 算法 刻板