动态规划

一、简介

复杂问题分阶段简化成简单问题，就是动态规划的思想。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

适合初学者用动画的方式来简单的理解什么是动态规划: 漫画解读：什么是动态规划？

1. 动态规划的三个关键点：

• 最优子结构（大问题拆成小问题）
• 边界（初始条件）
• 状态转移方程（用表达式表示）

2. 什么时候需要动态规划

• 重叠子问题
• 最优子结构
• 优化递归

3. 动态规划解题思路

• 核心思想是递推。
• 难点在于想清楚状态 dp[i] 代表什么，然后构造状态转移矩阵，利用初始条件递推出最终结果。
• 常用画表的方式记录小问题的结果，然后大问题再根据小问题的结果计算。

4. 无后效性

“未来与过去无关”，这就是无后效性。也就是说子问题已经计算出来的结果，不会受未来的因素而改变。

二、leetcode编程题练习

1. 爬楼梯: 动态规划最强入门题（LeetCode 70）

假设一个人正在爬楼梯。需要 n 阶才能到达楼顶。每次可以爬 1 或 2 个台阶。问共有多少种不同的方法可以爬到楼顶？

动态规划画表

|台阶数|0|1|2|3|4|5|6|7|8|9|10 |-|-|-|-|-|-|-|-|-|-|-|-|-|-| |走法数|0|1|2|3|5|8|13|21|34|55|89

• 最优子结构：F(n - 1)、F(n - 2)
• 边界： F(0) = 0、F(1) = 1、F(2) = 2
• 状态转移方程：F(n) = F(n - 1) + F(n - 2)

代码

/**
 * 方法1：递归
 * 缺点：时间复杂度太高
 * 时间：O(2^n)  空间：O(1)
 * @param {number} n 
 */
function comput1 (n) {
    if (n === 0) {return 0;}
    else if (n === 1) {return 1;}
    else if (n === 2) {return 2;}
    return comput(n - 1) + comput(n - 2);
}

/**
 * 方法2：缓存（备忘录）
 * 缺点：需要一个map映射
 * 时间：O(n)  空间：O(n)
 * @param {number} n 
 */
function comput2 (n) {
    const map = {0: 0, 1: 1, 2: 2};
    return computInner(n);
    function computInner(n) {
        if (map[n] === undefined) {
            map[n] = computInner(n - 1) + computInner(n - 2);
        }
        return map[n];
    }
}

/**
 * 方法3：动态规划
 * 状态转移方程：F(n) = F(n - 1) + F(n - 2)
 * 时间：O(n)  空间：O(1)
 * @param {number} n 
 */
function comput3 (n) {
    if (n === 0) {return 0;}
    else if (n === 1) {return 1;}
    else if (n === 2) {return 2;}
    let pree = 1, pre = 2, temp = 0;
    for (let i = 3; i <= n; i++) {
        temp = pree + pre;
        pree = pre;
        pre = temp;
    }
    return temp;
}


console.log(comput3(4));
console.log(comput3(10));

2. 打家劫舍（LeetCode 198）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例

输入： [2,7,9,3,1] 输出： 12 解释： 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

子问题

• 只考虑前两个房间时，谁大选谁
• 考虑第三个房间
  • 如果偷第三个房间，则意味着第二个房间不投，也就是第三个房间值 + 第一个房间的金额
  • 如果不偷第三个房间，则金额等于前两个房间金额
  • 上面两种方案取金额较大的一个

初始条件

dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

画表

状态转移方程

dp[i] = max(nums[i] + dp[i-2], dp[i-1])

代码

/**
 * @param {number[]} nums
 * @return {number}
 * F(n) = max(F(n - 2) + nums[n], F[n - 1])
 */
var rob = function(nums) {
    if (nums.length === 0) {return 0}
    const dp = [];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
    }
    return dp[nums.length - 1];
};

3. 三角形最小路径和(二维动态规划 LeetCode 120)

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例： 输入： triangle = [[2], [3,4], [6,5,7], [4,1,8,3]] 输出： 11 解释： 如下面简图所示：

2
3 4
6 5 7
4 1 8 3

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

最后必然经过最下方的几个元素之一出来，只需对比每一条出口的不同， 行数i，列数j min_j=03{ min_i=03{ F(i-1, j), F(i-1, i) } + a[i, j] }

画表

代码

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    let pre = triangle[0], cur = [].concat(pre);
    for (let i = 1; i < triangle.length; i++) {
        const row = triangle[i];
        for (let j = 0; j < row.length; j++) {
            const value = row[j];
            if (j === 0) {
                cur[j] = pre[j];
            } else if(j === row.length - 1) {
                cur[j] = pre[j - 1];
            } else {
                cur[j] = Math.min(pre[j], pre[j - 1]);
            }
            cur[j] += value; 
        }
        pre = [].concat(cur);
    }
    return Math.min.apply(null, cur);
};

4. 挖矿

问题：有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

画表

1个金矿

2个金矿

3个金矿

4、5个金矿

状态转移方程

假设金矿数量为n，工人总数为w，黄金量数组g[]，矿用工量数组p[]

状态转移方程：F(n, w) = max(F(n - 1, w), F(n - 1, w - p[4]) + g[n - 1])

时间：O(2^n) 空间：O(1)

代码

/**
 * 方法2：动态规划
 * 假设金矿数量为n，工人总数为w，黄金量数组g[]，矿用工量数组p[]
 * 状态转移方程：F(n, w) = max(F(n - 1, w), F(n - 1, w - p[4]) + g[n - 1])
 * 时间：O(2^n)  空间：O(1)
 * @param {Array<{gold: Number, worker: Number}>} list 金矿和需要的工人数
 * @param {Number} n 总共工人数
 */
function work2 (list, w) {
    const n = list.length;
    let pre = [];
    const result = [];
    result.length = pre.length = w + 1;
    pre.fill(0);
    result.fill(0);
    // 填充边界
    for (let j = 0; j <= w; j ++) {
        pre[j] = list[0].worker > j ? 0 : list[0].gold;
    }
    // 填充其余格子，外循环是金矿数，内循环是工人数
    for (let i = 0; i < n; i ++) {
        for (let j = 1; j <= w; j ++) {
            if (list[i].worker > j) {
                result[j] = pre[j];
            } else {
                const gold = list[i].gold + pre[j - list[i].worker]; // 挖第i个矿，其余人挖之前的矿
                result[j] = Math.max(pre[j], gold);
            }
        }
        pre = [].concat(result);
    }
    return result[w];
}

const list = [
    {gold: 400, worker: 5},
    {gold: 500, worker: 5},
    {gold: 200, worker: 3},
    {gold: 300, worker: 4},
    {gold: 350, worker: 3},
];
console.log(work2(list, 10));

5. 地下城游戏(无后效性 LeetCode 174)

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为_负整数_，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为_正整数_，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

说明:

• 骑士的健康点数没有上限。
• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

分析

如果按照从左上往右下的顺序进行动态规划，我们无法直接确定到达终点的方案，因为有两个重要程度相同的参数同时影响后续的决策。也就是说，这样的动态规划是不满足无后效性的。

于是考虑从右下往左上进行动态规划。令 dp[i][j]dp[i][j] 表示从坐标 (i,j)(i,j) 到终点所需的最小初始值。换句话说，当我们到达坐标 (i,j)(i,j) 时，如果此时我们的路径和不小于 dp[i][j]dp[i][j]，我们就能到达终点。

dp[i][j] 表示从坐标 (i,j)(i,j) 到终点所需的最小初始值。换句话说，当到达坐标 (i,j)(i,j) 时，如果此时的路径和不小于 dp[i][j]，就能到达终点。

画表

状态转移方程

F(i, j) = max { min{ F(i + 1, j), F(i, j + 1) } - a[i][j], 1 }

代码

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
var calculateMinimumHP = function(dungeon) {
    let pre = [], cur = [];
    const rows = dungeon.length - 1;
    for (let i = rows; i >= 0; i --) {
        const row = dungeon[i];
        const columns = row.length;
        for (let j = columns - 1; j >= 0; j --) {
            const value = row[j];
            if (i === rows && j === columns - 1) {
                cur[j] = Math.max(1 - value, 1);
            } else if (i === rows) {
                cur[j] = Math.max(cur[j + 1] - value, 1);
            } else if (j === columns - 1) {
                cur[j] = Math.max(pre[j] - value, 1);
            } else {
                cur[j] = Math.max(Math.min(cur[j + 1], pre[j]) - value, 1);
            }
        }
        pre = [].concat(cur);
    }
    return cur[0];
};

参考

• 漫画：什么是动态规划？
• leetcode|动态规划专项练习
• leetcode题解