动态规划

字数统计: 4.3k字   |   阅读时长: 16分

前言

Dynamic Programming学习。

概念

动态规划是研究多步决策过程最优化问题的一种数学方法。在动态规划中，为了寻找一个问题的最优解（即最优决策过程），将整个问题划分成若干个相应的阶段，并在每个阶段都根据先前所作出的决策作出当前阶段最优决策，进而得出整个问题的最优解。即记住已知问题的答案，在已知的答案的基础上解决未知的问题。

自底向上和自顶向下

记忆化搜索是一种自顶向下的动态规划实现。它通过递归调用并在计算过程中保存已计算结果（通常使用哈希表或数组），避免重复计算。这种方法主要用于优化递归算法。

动态规划通常是自底向上的实现。它通过构建表格（通常是二维数组或一维数组）来存储子问题的结果，然后根据这些结果来构建最终答案。这种方法适用于问题具有最优子结构和重叠子问题的性质。

所谓自顶向下，是指从问题的最上层开始解决，然后递归地解决子问题。通常在实现中会使用递归，并且在计算子问题时会存储结果，以避免重复计算，适合于问题较为复杂且子问题数量不确定的情况。

自底向上则是从最简单的子问题开始解决，然后逐步构建出更复杂的解决方案。通常使用迭代的方式，通过填充表格（数组）来实现，适合于子问题数量明确且可以直接计算的情况。

但有些时候二者的子问题是可以通用的，这点还需要多做多体会。

能解决的问题

1、计数问题
例如“有多少种方式使得…”，或者“有多少种方法选出…”。

2、最值问题
例如经典的“最少用多少枚硬币能组合出目标面值”，或者“求最长上升子序列”。

3、存在性问题
例如“能不能选出k个数使得…”，或者“先手方是否必胜”。

注意，通常求所有解法的问题不能用DP方法来做，因为与最优解无关的解在动态规划中不会被全部计算。

思想

在上述问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

这种记住子问题的做法很容易联想到记忆化，但 动态规划 和 记忆化搜索 的一个重要区别是动态规划通常不使用递归实现。 另外在计算顺序方面，多数动态规划问题是自底向上的（这与状态转移有关），而记忆化搜索是自顶向下的。

通常可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其最优解填入表中，方便在求解之后的子问题时可以方便调用，进而求出整个问题的最优解。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

也可以说，动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

解题思路

通常通过动态规划求解问题由四个主要部分组成：
1、拆分子问题
2、确定状态转移方程
3、确定初状态和边界条件
4、确定计算顺序

这四个部分看起来简单易懂，但是在实践过程中却会遇到重重困难。下面分别详细的解释一下。

首先需要明确动态规划解决的是一个多步决策问题，该问题由初状态、若干中间决策和末状态组成。

1、拆分子问题

拆分子问题，即将原问题拆解成为范围更小但性质不变的子问题。

一般首先要做的是找出“最后一步”，也就是若干中间决策的最后一步，经历该决策后，问题转变到末状态。

找到“最后一步”后，我们研究“最后一步”前的状态，它应该能够构成一个子问题，i.e.，如果说“最后一步”使问题达到末状态，且这一系列决策构成问题的最优解，那么去掉“最后一步”的决策链应该是最优解的一个子集，同时“最后一步”前的状态构成一个子问题，该子集为该子问题的最优解。

这样一来，我们就从原问题中拆出了一个子问题。拆分子问题的目的是找出状态，状态是对问题各阶段的客观表述，同时需要满足无后效性，即当前状态之后的决策对该状态无影响。

2、确定状态转移方程

状态转移方程是动态规划的重中之重，一旦确定了状态转移方程，问题通常也就迎刃而解了。

状态转移就是根据上一阶段的状态和之后的一次决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。 但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 状态转移方程通常是一个递推公式。

同时，状态转移方程也影响着最终算法的计算顺序，通常靠后的状态会需求前方状态的信息，原问题为求到最后状态的最优解，因此动态规划问题通常都是自底向上计算的。

我们用一个数组或哈希表来记录状态的最优解，本文暂时称其为状态表。

3、确定初状态和边界情况

初状态就是问题的初始状态。 确定初状态主要是确定状态表如何初始化。

边界情况也称边界条件，即状态转移方程的边界，有时在递推公式的某一部分会出现不合理的或不属于问题范围内的项，需要通过边界条件来限制它。

4、确定计算顺序

如上面所说的，根据状态转移公式来确定。

案例一：摩天大楼

题目如下：

skyscraper

拿到题目我们首先考虑一下暴力法，从暴力法的实现中可以看出有没有优化的余地，下面是我手写的一个过程，以输入$[2, 5, 1, 4, 8]$为例。

bf

可以发现有很多重复计算，可以通过记忆化进行优化。 暴力法代码如下：

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
# author：SilenceZheng66

def brutal_force(L: list[int]):
    n = len(L)

    results = []

    if n <= 1:
        return 0

    def to_top(pos, times):
        if pos == n - 1:
            results.append(times)
        else:
            for j in range(pos + 1, pos + L[pos] + 1):
                if j < n:
                    to_top(j, times + 1)

    if L[0] >= n - 1:
        results.append(1)
    else:
        for i in range(1, L[0] + 1):
            if i < n:
                to_top(i, 1)

    return min(results)

下面我们开始用动态规划的解题步骤尝试去优化我们的算法。

1、拆分子问题

原问题是：找出从底层到楼顶的最少乘电梯数。我们以数组的下标$pos$来进行说明，底层的$pos = 0$，楼顶的$pos = n-1$。

假设“最后一步”前的状态为 $pos = m$ ，那么“最后一步”就是 $n-1$ 位于 $m + 1$ 和 $m + L[m]$ 之内，也可以表示为 $m + L[m] \geq n-1$。 此时原问题就被拆分成了子问题：找出从底层到$m+1$层的最少乘电梯数。 原问题的答案为该子问题答案$+1$。

那么此时我们就可以描述状态了，$f(x) = 到达x层的最少乘电梯数$。

2、确定状态转移方程

第一步中我们拆分了子问题，确定了状态$f(x)$，则原问题可以描述为状态表中的最后一个状态，即$f(n-1)$。 根据“最后一步”中的推断，最理想的状态是能直接找到$f(n-1)$的前一个最优状态$f(m)$，然后再找到$f(m)$的前一最优个状态…直到正好找到$f(0)$。但是这是不可能实现的。

回到现实，还是考虑输入$[2, 5, 1, 4, 8]$，很自然的能够得出$f(4) = min(f(3), f(1)) + 1$，那么问题来了，为什么不是$min(f(3),f(2),f(1),f(0))$？很明显，我们需要考虑电梯的上升能力，即$5$层前有哪些层是能直接到达$5$层的？这些能直接到达的层里，哪些层的$f(x)$最小？找出他们，再加上$1$，就得到了$f(4)$。

基于以上分析，我们可以得出状态转移方程：

其中$g(f(x-1), … ,f(0))$表示从$pos=0$到$pos=x-1$中选出那些满足$L[pos] + pos \geq x $的$f(pos)$。

得出了状态转移方程，这道题也就拿下来一多半了。

3、确定初状态和边界情况

初状态是好确定的，因为要做求最小运算，所以状态表初始化时所有元素应为系统能取到的最大正整数值。而$f(0)$应该被置为$0$，因为到达ground floor的最少乘电梯次数是$0$次。

关于边界情况，可以看到状态转移方程中有涉及到$L[pos] + pos$的运算，这可能会超出数组上界，故需要考虑进去。 同时如果大楼的层数$\leq 1$，则可以直接得出$f(n-1) = f(0) = 0$，也可以考虑进去。

4、确定计算顺序

从状态转移公式可以看出，靠后的状态依赖前方状态信息，故应为自底向上。

最后就是写代码了，这里提供一个我写的示范。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# author：SilenceZheng66

def dp(L: list[int]):
    n = len(L)

    # 状态数组
    conditions = [sys.maxsize for _ in range(n)]

    # 初始状态
    conditions[0] = 0

    # 边界情况
    if n <= 1:
        return 0

    # 自底向上
    for i in range(n - 1):
        # 边界情况判断
        for j in range(i + 1, i + L[i] + 1) if i + L[i] + 1 <= n else range(i + 1, n):
            conditions[j] = min(conditions[i] + 1, conditions[j])

    return conditions[-1]

案例二：比特位计数

Leetcode的一道简单题，但有三种DP官解，很适合练习思路。

题目：给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

先考虑暴力法，外层循环肯定是必要的，对1计数的话，我的想法是从最低位一直与一做与操作，然后逻辑右移，这样内层就是固定32次，外层n次：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// author: SilenceZheng66
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];

        for(int i=0;i<=n;i++){
            int count = 0;
            int tmp = i;

            for(int j=0;j<32;j++){
                if((tmp&1)==1) count++;
                tmp>>>=1;
            }

            ans[i] = count;
        }

        return ans;
    }
}

那么这种方式有没有重复计算的地方呢？不妨用数字10举例，对于数字10（1010），在计算一次最低位后，剩余部分是之前已经计算过的数字5（0101）。那么可以采用记忆化方法，这样一来能提高不少效率：

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
// author: SilenceZheng66
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n+1];

        for(int i=0;i<=n;i++){
            int count = 0;
            int tmp = i;
            ans[i] = -1;

            for(int j=0;j<32;j++){
                if(ans[tmp]!=-1){
                    count+=ans[tmp];
                    break;
                }
                if((tmp&1)==1) count++;
                tmp>>>=1;
            }

            ans[i] = count;
        }

        return ans;
    }
}

好了，以上是我对这道题的思路，但是对于以上解法，我没有想出如何使用DP来优化，下面是官解思路。

官解首先提出了另一个计算1bit数量的算法，即对于任意整数 x，令 x = x&(x-1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。 该方法称为Brian Kernighan 算法。

利用这个计数法写出暴力法不是什么难事：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// author: LeetCode-Solution
class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }

    public int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }
}

下面开始用动态规划的解题步骤尝试去优化此算法。

1、拆分子问题

首先需要明确该案例与案例一的区别，案例一为“最值问题”，显然可使用动态规划求解。而该案例并不明显的属于前文所提到的三类问题中的某一类，为什么可以由采用DP求解呢？我个人的理解是，题目要求返回的序列中后方的信息可以依赖前方的信息求出，这暗中符合了状态转移的性质，如若独立对每一项进行计算，则会出现计算冗余，此时采用DP是合适的。

在我的解法中，已经体现了一部分借助前方信息的思想，但并没有整理出一个状态转移方程，仅仅是简单的记忆化。现在，基于Brian Kernighan算法，我们来寻找一种使用动态规划解决问题的方法。

对于该问题，可以很明显的找到“最后一步”，即求n的二进制表示中的1bit数，我们将其记为$bits[n]$那么去除掉最后一步后的子问题就变为了“求$0$到$n-1$的$1$比特位计数序列”。原问题的答案为该子问题的答案$bits[0…n-1]$+$bits[n]$。

那么此时我们可以描述状态为$f(x) = 在求出0到x-1序列的基础上，求x的二进制表示中的1比特数量$。

2、确定状态转移方程

状态转移方程是DP的关键，这道题有很多状态转移的思路，这里介绍从最高有效位入手的思路。

对于正整数$x$，若可以知道最大正整数$y$，使得$y\leq x$且$y$是$2$的整数次幂，则$y$的二进制表示中只有最高位是$1$，其余为$0$。此时将$y$称为$x$的最高有效位。则显然存在$z = x - y, 0 \leq z \le x$，有$bits[x] = bits[z] + 1$。根据上述推导，我们可以发现$y, z$都落在$bits[0…x]$中，我们只需要找到对$x$求$y$的方法即可，但这个方法一定要高效，在$O(1)$里计算。

可以利用y&(y-1)==0来判断，因为$y$中仅含有一个最高位$1$，也就是说正整数$y$是$2$的整数次幂，当且仅当y&(y-1)==0。由于我们自底向上进行求解，数字$x$的最高有效位逐步递增，我们可以在遍历的过程中更新$y$。

至此，我们可以写出状态转移方程：

3、确定初状态和边界情况

初状态自然就是$f(0)$了，此时$bits[0]=0$。

边界的话，不存在越上界的情况，下界保证初状态不越界即可。

4、确定计算顺序

计算顺序自底向上，最终代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// author: LeetCode-Solution
class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}

5、其他思路

除了从最高有效位出发以外，从我原本的思路出发也可以转化到DP解法，即最低有效位方式。

其核心思想是$bits[x]$的值等于$\textit{bits}\big[\lfloor \frac{x}{2} \rfloor\big]$的值加上$x$除以$2$的余数。用代码表示就是bits[x] = bits[x>>1] + (x&1)。代码如下：

1
2
3
4
5
6
7
8
9
10
// author: LeetCode-Solution
class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

后记

首发于 silencezheng.top，转载请注明出处。

赏

谢谢打赏哟！

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

SilenceZheng66<br><br>记录所学技术<br>谢谢浏览