Dynamic Programming 动态规划

September 25, 2022 11648

开篇废话

时隔一年，又开始了我的算法生涯。唉，苦海无边，人生有涯啊。
这次先来看看DP，DP难在找到递归式和边界值。

流程

动态规划问题的一般形式就是求最值，求解的核心问题是穷举，然后找最值。
动态规划的一般流程就是三步：暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法
具体来说，利用递归思维列出正确的 「状态转移方程」，判断算法问题是否具备 「最优子结构」，即能否通过子问题的最值得到原问题的最值，再判断是否需要用「备忘录」或者「DP table」来优化穷举过程，解决 「重叠子问题」。
思考步骤：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

单串经典问题

最长递增子序列（Longest Increasing Subsequence，LIS）

模版

  1. 嵌套遍历
  2. binary search
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    ## 朴素版
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int index = 0;
        dp[index] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[index] < nums[i]) {
                dp[++index] = nums[i];
            } else {
                int l = 0, r = index;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if (dp[mid] < nums[i]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                dp[l] = nums[i];
            }
        }
        return index + 1;
    }
    ## API版本
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }

问题

参考

最大子数组和

模版

1
2
3
4
5
6
// Kadane's algorithm
max = cur = None
for x in A:
    cur = x + max(cur, 0)
    max = max(max, cur)
return max

矩阵的话，方法类似：算出每一列的前缀和，然后遍历所有情况的行组合。O(n^2m)

问题

最大子数组和变体：House Robber

模版

1
2
3
4
5
6
7
pre1 = pre2 = max = cur = None
for x in A:
    cur = x + max(pre2, 0)
    pre2 = pre1
    pre1 = max(pre1, cur)
    max = max(max, cur);
return max

问题

需要两个位置的情况

问题

其他

问题

带维度的单串！！

增加维度，通常用 k 表示，k 随着题目的不同，可以表示长度，个数，次数，颜色等，同时 k 这个维度的枚举和转移可能涉及到二分，贪心等算法

问题

买卖股票

双串经典问题

最长公共子序列(LCS)

其他

问题

矩阵问题

无串问题

前缀和

单纯实现

问题

数据结构维护前缀和

常见数据结构

  • 哈希表
    • 键是前缀和（状态）的值，值为第一次出现时的索引
    • 键是前缀和（前缀状态）的值，值为出现次数
    • 键是前缀和模 K 的余数（可以理解为前缀状态，状态为前缀和模K）
  • 二维数组
  • 线段树
  • 其他：
    • 前缀和（积）与后缀和（积）均需要
    • 二维前缀和

问题

区间动态规划

回文系列

下面的我一道都不会，被自己蠢哭了【放弃。想转行了

未归类，我还没做，等慢慢做吧

Reference: