Notes

# 动态规划

动态规划（dynamic programming）是解决多阶段决策问题常用的最优化理论，该理论由美国数学家Bellman等人在1957年提出，用于研究多阶段决策过程的优化问题。该理论提出后，立即在数学、计算机科学、经济管理和工程技术领域得到了广泛的应用，例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法往往比朴素的方法更高效。动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。

动态规划适合求解多阶段（状态转换）决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题，但是这些问题都必须满足最优化原理和子问题的“无后向性”。

  • 最优化原理：最优化原理其实就是问题的最优子结构的性质，如果一个问题的最优子结构是不论过去状态和决策如何，对前面的决策所形成的状态而言，其后的决策必须构成最优策略。也就是说，不管之前决策是否是最优决策，都必须保证从现在开始的决策是在之前决策基础上的最优决策，则这样的最优子结构就符合最优化原理。
  • 无后向性（无后效性）：所谓“无后向性”，就是当各个阶段的子问题确定以后，对于某个特定阶段的子问题来说，它之前的各个阶段的子问题的决策只影响该阶段的决策，对该阶段之后的决策不产生影响，也就是说，每个阶段的决策仅受之前决策的影响，但是不影响之后各阶段的决策。

动态规划的基本思想 和分治法一样，动态规划解决复杂问题的思路也是对问题进行分解，通过求解小规模的子问题再反推出原问题的结果。但是动态规划分解子问题不是简单地按照“大事化小”的方式进行的，而是沿着决策的阶段划分子问题，决策的阶段可以随时间划分，也可以随着问题的演化状态划分。分治法要求子问题是互相独立的，以便分别求解并最终合并出原始问题的解，但是动态规划法的子问题不是互相独立的，子问题之间通常有包含关系。

动态规划法不像贪婪法或分治法那样有固定的算法实现模式，作为解决多阶段决策最优化问题的一种思想，它没有具体的实现模式，可以用带备忘录的递归方法实现，也可以根据堆叠子问题之间的递推公式用递推的方法实现。但是从算法设计的角度分析，使用动态规划法一般需要四个步骤，分别是定义最优子问题、定义状态、定义决策和状态转换方程以及确定边界条件，这四个问题解决了，算法也就确定了。

# 背包问题

An image

function dKnapsack(capacity, size, value, n) {
		const K = new Array(n+1).fill(0).map(() => new Array(capacity+1).fill(0));

		for (let  i = 1; i <= n; i++) {
			for (let w = 1; w <= capacity; w++) {
				if (size[i-1] <= w) {
					K[i][w] = Math.max(value[i-1] + K[i-1][w-size[i-1]], K[i-1][w]);
				} else {
					K[i][w] = K[i-1][w];
				}
			}
		}
		return K[n][capacity];
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 53. 最大子序和

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

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre = 0, max = nums[0];
    nums.forEach(x => {
        pre = Math.max(pre + x, x);
        max = Math.max(max, pre);
    });
    return max;
};
1
2
3
4
5
6
7
8
9
10
11
12

# 338. 比特位计数

中等给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 详细 (opens new window)

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
    const ans = new Array(num + 1).fill(0);
    let highBit = 0;
    for (let i = 1; i <= num; i++) {
        if ((i & (i - 1)) == 0) {
            highBit = i;
        }
        ans[i] = ans[i - highBit] + 1;
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 518. 零钱兑换 II

中等给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 详细 (opens new window)

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

← 贪心算法 →