CHIEMINCHAN'S BLOG

# 👉 动态规划

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如让你求最长递增子序列、最小编辑距离等等。

在深度遍历时有提及过，当解需要穷举列出所有详细路径时，则需要往递归/回溯方向考虑。

而动态规划一般是要求最值，动态规划的穷举有点特别，因为这类问题 存在「重叠子问题」 ，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

摘取来自修言小册的一段话：什么样的题应该用动态规划来做？我们要抓以下两个关键特征：最优子结构和重叠子问题。

最优子结构，它指的是问题的最优解包含着子问题的最优解——不管前面的决策如何，此后的状态必须是基于当前状态（由上次决策产生）的最优决策。就这道题来说，f(n)和 f(n-1)、f(n-2)之间的关系印证了这一点（这玩意儿叫状态转移方程，大家记一下）。

重叠子问题，它指的是在递归的过程中，出现了反复计算的情况。

# 动态规划的解题思路

对于动态规划，建议大家优先选择这样的分析路径：

  1. 递归思想明确树形思维模型：找到问题终点，思考倒退的姿势，往往可以帮助你更快速地明确状态间的关系
  2. 结合记忆化搜索(提供一个 map 存储子问题最优解)，明确状态转移方程
  3. 递归代码转化为迭代表达。

推荐教程：

# 应用

# 爬楼梯

# 背包模型

背包问题具备的特征：给定一个 target，target 可以是数字也可以是字符串，再给定一个数组 nums，nums 中装的可能是数字，也可能是字符串，问：能否使用 nums 中的元素做各种排列组合得到 target。

https://leetcode-cn.com/problems/combination-sum-iv/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-wen-/

# 0-1 背包模型

如果是 0-1 背包，即数组中的元素不可重复使用，nums 放在外循环，target 在内循环，且内循环倒序

有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？注意：每种物品都只有 1 件

function knapsack(capacity, objectArr) {
    const dp = [0];

    // dp[i+1]表示i的容量的最大价值

    for (let i = 1; i <= capacity; i++) {
        dp[i] = 0;

        for (let j = 0; j < objectArr.length; j++) {
            // 每个物品都有选和不选的选择，仅可在没超出最大容量的时候进行选择
            const { weight, value } = objectArr[j];
            if (i >= weight) {
                // 选，dp[i] = values[j] + dp[capaticy - weight[j]];
                // 不选，dp[i] = dp[i];
                dp[i] = Math.max(dp[i], dp[capacity - weight] + value);
            } else {
                // 超出最大容量的时候，不能选，只能选为上个容量的最大价值
                dp[i] = Math.max(dp[i - 1], dp[i]);
            }
        }
    }

    return dp[capacity];
}

0-1 背包问题子结构：选择一个给定第 i 件物品，则需要比较选择第 i 件物品的形成的子问题的最优解与不选择第 i 件物品的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。

# 完全背包

如果是完全背包，即数组中的元素可重复使用，nums 放在外循环，target 在内循环。且内循环正序。

for num in nums:
    for i in range(nums, target+1):

# 组合问题

如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 nums 放在内循环

for i in range(1, target+1):
    for num in nums:

给定一个正整数 s, 判断一个数组 arr 中，是否有一组数字加起来等于 s

// 递归
const rec_subset = function(arr, i, s) {
    // 2. 分析退出边界情况
    if (s === 0) {
        return true;
    } else if (i === 0) {
        return arr[0] === s;
    } else if (arr[i] > s) {
        // arr[i] > s，直接跳过不选，因为它比s大
        return rec_subset(arr, i - 1, s);
    } else {
        // 1. 分析dp工程式，一份以选或者不选的情况展开
        const A = rec_subset(arr, i - 1, s - arr[i]);
        const B = rec_subset(arr, i - 1, s);
        return A || B;
    }
};

const arr = [3, 34, 4, 12, 5, 2];
console.log(rec_subset(arr, arr.length - 1, 9)); // true

// 3. 分析dp工程式，将递归转成迭代（往后退的思维）

// 非递归
const dp_subset = function(arr, sum) {
    // 构造一个(len * sum+1)维数组
    const subset = new Array(arr.length);
    // 初始化这个subset数组

    // 当sum=0时，不管到达哪个元素都为true
    for (let i = 0; i < arr.length; i++) {
        subset[i] = [];
        subset[i][0] = true;
    }

    // 当sum = arr[0]时，才会返回true，其他都是false
    for (let i = 0; i <= sum; i++) {
        subset[0][i] = arr[0] === i;
    }

    for (let i = 1; i < arr.length; i++) {
        for (let s = 1; s <= sum; s++) {
            // s比当前值大，则直接不能选，只能 看不选它的情况是否为真
            if (arr[i] > s) {
                subset[i][s] = subset[i - 1][s];
            } else {
                // 选i
                const a = subset[i - 1][s - arr[i]];
                // 不选i
                const b = subset[i - 1][s];

                subset[i][s] = a || b;
            }
        }
    }

    console.log(subset);

    return subset[arr.length - 1][sum];
};
const arr = [3, 4, 5, 1, 2];
console.log(dp_subset(arr, 3));

# 最长上升子序列模型

关于这道题，提供一个比较详细的讲解过程：https://juejin.cn/post/6952674285311754276

var jobScheduling = function(startTime, endTime, profit) {
    // 整理数组，将每份工作的开始、结束、报酬合并
    let jobArr = new Array(profit.length);
    for (let i = 0; i < profit.length; i++) {
        jobArr[i] = [startTime[i], endTime[i], profit[i]];
    }

    // 按结束时间从小到大排序
    jobArr.sort(([a1, a2], [b1, b2]) => {
        return a2 - b2;
    });

    // 存储接受每份工作时的最大报酬（从1开始,0表示都不做）
    const dp = [0];
    dp[1] = jobArr[0][2];

    for (let i = 1; i < jobArr.length; i++) {
        // 计算如果选了当前i，还能选前面的哪些工作，即作为prev
        // 最坏的情况是选了i，前面的都不能再选了
        let prev = -1;

        for (let j = i - 1; j >= 0; j--) {
            // const [startTime, endTime, profit] = jobArr[i];
            // 当且仅当j的endTime小于等于当前的startTime才可以作为prev
            if (jobArr[j][1] <= jobArr[i][0]) {
                prev = j;
                // 得到prev要及时退出
                break;
            }
        }

        // 不选i的情况下，求opt(i-1)
        // 选的时候，opt(prev)+vi

        // 选i, prev相对dp是prev+1
        let num1 = jobArr[i][2] + dp[prev + 1];
        // 不选i
        let num2 = dp[i];

        dp[i + 1] = Math.max(num1, num2);
    }

    return dp[jobArr.length];
};

← 👉 排序（从小到大） →