Ji Xiang's blog

动态规划

Posted on

动态规划算法的思路以及实现

介绍

动态规划(DP)是算法设计思想当中最难也是最有趣的部分了，动态规划适用于有重叠子问题和最优子结构性质的问题，是一种在数学、计算机科学和经济学中经常使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。使用动态规划方法解题有较高的时间效率，关键在于它减少了很多不必要的计算和重复计算的部分。

它的思想就是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要的性质才能进行动态规划：

  • 最优子结构性：既所拆分的子问题的解是最优解。
  • 子问题重叠性质：既在求解的过程当中，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。

示例

首先引用一道动态规划的经典问题最长不下降子序列
它的定义是：设有由n个不相同的整数组成的数列 b[n]，若有下标 i1 < i2 < … < iL 且 b[i1] < b[i2] < … < b[iL]
则称存在一个长度为 L 的不下降序列。

例如

13, 7, 9, 16, 38, 24, 37, 18, 44, 19, 21, 22, 63, 15

那么就有 13 < 16 < 38 < 44 < 63 长度为5的不下降子序列。
但是经过观察实际上还有 7 < 9 < 16 < 18 < 19 < 21 < 22 < 63 长度为8的不下降子序列，那么是否还有更长的不下降子序列呢？请找出最长的不下降子序列。

输入格式

第一行为 n，表示 n 个数(n <= 100000)，第二行为 n 个数的数值(数字之间用空格隔开且最后一个数字末尾不能留有空格)。

输出格式

一个整数，表示最长不下降序列的长度。

输入例子

4
1 3 1 2

输出例子

2

思路

假如要求得某一段的最优，就要想更小段的最优怎么求，再看看由最小段的最优能否扩大推广到最大段的最优。所以该问题存在最优子结构，而从小段的最优子结构到更大的最优子结构，所有子结构的求解问题是相同的，即满足动态规划的性质。

假设这么一个表：

序列下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13
序列数值 13 7 9 16 38 24 37 18 44 19 21 22 63 15
序列长度 1 1 1 1 1 1 1 1 1 1 1 1 1 1
链接位置 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

第三行表示该序列元素的所能连接的最长不下降子序列的长度，因为本身长度为1，所以初始值都为1。
第四行表示链接于哪个序列元素形成最长不下降子序列。

1.从后向前

先从倒数第二项 63 算起，在它的后面仅有一项，因此仅作一次比较，因为 63 > 15，所以从 63 出发，不作任何链接，长度还是为1。

再看倒数第三项 22，在它的后面有 2 项，因此必须要在这 2 项当中找出比 22 大，长度又是最长的数值作为链接，由于只有 22 < 63，所以修改 22 的长度为 2，即自身长度加上所链接数值的长度，并修改链接位置为 13，也就是 63 的下标。

再看倒数第四项 21，在它的后面有 3 项，因此必须要在这3项当中找出比 21 大，长度又是最长的数值作为链接(注意:是长度)，很容易看出，数值 22 满足该条件，因此，修改 21 的长度为3，并修改链接位置为 12，即 22 的序列下标。

依次类推，最后结果如下表：

序列下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13
序列数值 13 7 9 16 38 24 37 18 44 19 21 22 63 15
序列长度 7 8 7 6 3 4 3 5 2 4 3 2 1 1
链接位置 3 2 3 7 8 6 8 9 12 10 11 12 -1 -1

最终状态的转移方程为：f(i) = maxf(j) + 1 (bj > bi 且 i < j)，时间复杂度为 O(n^2)

2.从前向后

序列下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13
序列数值 13 7 9 16 38 24 37 18 44 19 21 22 63 15
序列长度 1 1 2 3 4 4 5 4 6 5 6 7 8 3
链接位置 -1 -1 1 2 3 3 5 3 6 7 9 10 11 2

最终状态的转移方程为：f(i) = maxf(j) + 1 (bj < bi 且 i > j)，时间复杂度为 O(n^2)

代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
process.stdin.setEncoding('utf8');

var arr = [], // 接收输入参数的数组
    bool = 0, // 判断是否满足输入条件
    n = 0, // 数列元素个数
    longest = 1, // 最长不下降子序列长度
    a = [], // 数列元素数组
    dp = []; // 动态规划过程中子序列长度数组

process.stdin.on('readable', function() {
    var chunk = process.stdin.read();
    if(chunk !== null) {
        arr.push(chunk.trim());
    }

    if(bool >= 2) {
        n = parseInt(arr[0]);
        process.stdin.emit('end');
    }

    bool++;
});

process.stdin.on('end', function() {
    a = arr.slice(1).join(" ").split(" ").map(function(index, elem) {
        return parseInt(index);
    });
    if(n !== a.length) {
        process.stdout.write('长度不一致');
        return;
    }

    for(let i = 0; i < n; i++) {
        seq[i] = -1;
        dp[i] = 1;
    }

    for(let i = 1; i < n; i++) {
        for(let j = 0; j < i; j++) {
            if(a[i] > a[j]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
                (function(index, arg) {
                    seq[index] = arg;                    
                })(i, j);
            }
            longest = Math.max(dp[i], longest);
        }
    }
    
    console.log(`最长长度为：${longest}`);

    process.stdout.write('end');
});

输入输出

1
2
3
4
14
13 7 9 16 38 24 37 18 44 19 21 22 63 15
最长长度为：8
end