本文介绍一种经典的算法思想：动态规划

官方文邹邹定义：将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。
个人理解：未来取决于当下，脱钩于过去
使用DP的场景：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

经典算法必须有经典场景：斐波那契数列。
这种数列的一个最大特点： 初始值：f(1) = 1, f(2) = 1,之后的每一项都是前两项的和。所以f(3) = f(1) + f(2) = 2….

1. 爬楼梯

爬楼梯的方式有两种，一次一级或者两级，那么跳到n级，有多少种跳法？
实际就是一个斐波拉契数列，f(1) = 1, f(2) = 1…

const climbStairs = function(n) {
    if (n <= 1) return 1
    const f = [1,2]
    for (let i = 2; i < n; i++) {
        f[i] = f[i-1] + f[i-2]
    }
    return f[n-1]
};

这里可能难以理解的是，f(i)为什么要等于f(i -1) + f(i-2),这俩为什么要相加？列出所有可能性解释
f(1): [1]
f(2): [1,1], [2]
f(3): [1,2], [1,1,1], [2,1]
…
…
排列出来就看得很清晰了。要想到达f(3),只有两种可能：要么在第一级跳两级，要么在第二级出发跳一级，完毕

2. 最长公共子串

双指针逼近：暴力超时版本

function LCS( str1 ,  str2 ) {
    // write code here
    const min = str1.length < str2? str1: str2
    const max = str1.length < str2? str2: str1
    let res = ''
    for (let i =0; i < min.length; i++) {
        for (let j = min.length - 1; j>= 0; j--) {
            const cur = min.slice(i, j+ 1)
            if (max.includes(cur)) {
                if (res.length < cur.length) {
                    res = cur
                }
            }
        }
    }
    return res
}
// 复杂度o(n平方)

动态规划版本

function LCS( str1 ,  str2 ) {
    // write code here
    const dp = new Array(str1.length + 1);
    let max = 0;
    const map = new Map()
    for (let i = 0; i <= str1.length; i++) { // 初始化整个dp矩阵，每个值为0
      dp[i] = new Array(str2.length + 1).fill(0);
    }
     
    for(let i = 1;i<=str1.length;i++){
        for(let j = 1;j<=str2.length;j++){
            if(str1[i-1] === str2[j-1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
                max = Math.max(max,dp[i][j])
                if(!map.has(max)) map.set(max,i)  //避免重复
            }
        }
    }
    let startIndex = map.get(max) - max;
    let endIndex = map.get(max) ;
    return str1.substring(startIndex,endIndex)  //截取字符串
}

脑容量有限，愣是没看懂…

3. 不同路径: 一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？

思路： 因为只能往右或者往下，因此所有第一行i=0或者第一列j=0的路径均为1.那么从（1，1）开始的每一个格子的路径数目，取决于[i -1, j]和[i, j -1].代码如下：

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param m int整型 
 * @param n int整型 
 * @return int整型
 */
function uniquePaths( m ,  n ) {
    // write code here
    const res = Array(m).fill(Array(n).fill(1))
    const arr = Array(m).fill(Array(n).fill(1))
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            res[i][j] = res[i-1][j] + res[i][j-1]
        }
    }
    return res[m - 1][n -1]
}
module.exports = {
    uniquePaths : uniquePaths
};

4. 矩阵的最小路径和。给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

思路：此问题的思路同3是一致的。代码如下：

function minPathSum( matrix ) {
    // write code here
    const m = matrix.length
    const n = matrix[0].length
    // const res = Array(m).fill(Array(n).fill(0))
    const res = Array(matrix.length).fill(0).map(() => Array(matrix[0].length).fill(0));
    res[0][0] = matrix[0][0]

    for (let i = 1; i < n; i++) {
        res[0][i] = res[0][i-1] + matrix[0][i] 
    }
    for (let i = 1; i < m; i++) {
        res[i][0] = res[i-1][0] + matrix[i][0] 
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            res[i][j] = Math.min(res[i-1][j], res[i][j-1]) + matrix[i][j]
        }
    }
    return res[m- 1][n-1]
}

此题实际上同上一题几乎一样，单独拎出来的原因，在于注释掉的那一行。

const res = Array(m).fill(Array(n).fill(0))

这种初始化声明的方式会产生一个奇怪的现象：

res[0][0] = matrix[0][0]

一个简单的赋值发现，每一个内层数组的第一项，都被自动赋值…原因暂未查明-_-

最后，把坑填上。之前贪心算法篇中遗留的一个问题: 贪心算法的鼠目寸光，导致的结果错误。出一个动态规划的方案

// 一个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
// 这里默认三项哈
const f = (arr, target) => {
    const all = [0]
    arr.sort((a, b) => {
        return b - a
    })
    for (let i = 1; i <= target; i++) {
        all[i] = Math.min((i -arr[0]) >= 0? all[i -arr[0]]: 1, (i -arr[1]) >= 0? all[i -arr[1]]: 1, (i -arr[2]) >= 0? all[i -arr[2]]: 1) + 1
    }
    return all[target]
    
}
const arr = [1, 5, 11]
let target = 15
console.log(f(arr, target))
// 输出最优解：3

无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

5. 求出最大和的连续子数组

// 找出和最大的连续字数组


const arr = [-1, 4, -5, 3, 9, -1]

// 1. 复杂度n平方，双层for循环
const f = () => {
    let max = -Infinity
    let res = null
    for (let  i = 0; i < arr.length; i++) {
        for (let j = i; j < arr.length; j++) {
            const cur = arr.slice(i, j + 1)
            const sum = cur.reduce((prev, item, index) => {
                return prev + item
            }, 0)
            if (sum >= max ) {
                res = [...cur]
                max = sum
            }
        }
    }
    return res
}

// console.log(f())

// 2. 复杂度n
const f2 = () => {
    let sum = 0
    let ans = arr[0]
    for (let i = 0; i < arr.length; i++) {
        if (sum >= 0) {
            sum = sum + arr[i]
        } else {
            sum = arr[i]
        }
        ans = Math.max(ans, sum)
    console.log('sum:',sum)

    }
    return ans
}
console.log(f2())

总结：仔细思考会发现，所谓的动态规划实际上是存在上帝视角的，为了达到某一个目标，我们索性罗列出了几乎所有的可能，然后选取了最优解。而贪心算法则是每一步都选取了最优解，以期达到最终的最优解。拿人生举例脑海中突然出现了一个画面：一个站在上帝视角玩人生这个主进程游戏，一出场便光速的通过动态规划走完了全程，然后选去了一个最优解。另一个则是一步一个脚印，摸着石头过河，每次选择最优解，直到生命的尽头。在人生的这个特定场景下，贪心算法，才是最优解，因为不存在上帝，我们自己就是上帝。