一.动态规划算法

dynamic programming被认为是一种与递归相反的技术，递归是从顶部开始分解，通过解决掉所有分解出的问题来解决整个问题，而动态规划是从问题底部开始，解决了小问题后合并为整体的解决方案，从而解决掉整个问题。

动态规划在实现上基本遵循如下思路，根据边界条件得到规模较小时的解，小规模问题合并时依据递推关系式进行，也就是说较大规模的问题解可以由较小问题的解合并计算得到。最经典易懂的就是使用递归算法和动态规划算法两种不同的方式来计算斐波那契数列或求阶乘的对比，动态规划算法的特性相当于对计算过程进行了缓存，避免了不必要的重复计算。

本篇通过几个典型的相关实例来学习和练习动态规划算法。

二.寻找最长公共子串

题目不难理解，例如在单词“raven”和“havoc”的最长公共子串就是av。最容易想到的算法就是暴力求解，也称为贪心算法，在下一篇中会提供贪心算法暴力求解最长公共子串的示例代码。

算法描述如下：

字符串1长为m,字符串2长为n,先生成一个m*n的矩阵L并将其中都填充为0，矩阵中的值L[x,y]表示如果存在公共字符串，那么该字符串在字符串1中的位置为从x-L[x,y]到x，在字符串2中的位置为从y-L[x,y]到y，换句话说：L[x,y]记录了如果当前位置为公共子串的截止点时公共子串的长度。

递推关系式如下:

若str1[x] === str2[y], L[x,y] = L[x-1,y-1] + 1;

若str1[x] !== str2[y], L[x,y] = 0;

从图中可以更清晰地看到动态规划算法在寻找公共子串时的过程：

该表从左上角开始填空，循环遍历每个格子，如果str1中的字符和str2中的某个字符相同，则需要找到其左上角格子的数字，然后加1填在自己的格子里，如果不相等则填0，最终记录表中最大的值即为最长公共子串的结束位置，打印出最长公共子串也就很容易实现了。

参考代码：

/**  * 动态规划求解最长公共子串  */ function lcs(str1,str2) {     let record = [];     let max = 0;     let pos = 0;     let result = '';     //初始化记录图     for(let i = 0; i < str1.length; i++){         record[i] = [];         for(let j = 0; j < str2.length; j++){             record[i][j] = 0;         }     }     //动态规划遍历     for(let i = 0; i < str1.length; i++){         for(let j = 0; j < str2.length; j++){             if (i === 0 || j === 0) {                 record[i][j] = 0;             }else{                 if (str1[i] === str2[j]) {                      record[i][j] = record[i-1][j-1] + 1;                 } else {                      record[i][j] = 0;                 }             }             //更新最大值指针             if (record[i][j] > max) {                 max = record[i][j];                 pos = [i];             }         }     }     //拼接结果     if (!max) {         return '';     } else {         for(let i = pos ; i > pos - max ; i--){             result = str1[i] + result;         }         return result;     } }  console.log(lcs('havoc','raven')) console.log(lcs('abbcc','dbbcc'))

三.0-1背包问题递归求解

0-1背包问题用递归或动态规划都可以求解，通过本例和下一节的例子就可以对比两种算法相反的求解过程。

背包问题是算法中一个经典的大类，从简单到复杂一本书都讲不完，本例中仅实现简单的0-1背包问题，这类问题是指被放入背包的物品只能选择放或者不放，不能只放入一部分。

0-1背包问题的描述是这样的，假设保险箱中有n个物品，他们的尺寸存放在