Boil's Blog HomeArchivesTagsCategories
动态规划第一讲
Word count: 2.5k|Reading time: 10 min

动态规划方法的总体思想是什么，比较它与分治法的异同

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题

但是经分解得到的子问题往往不是互相独立的。用分治法来解，最后解决原问题需要耗费指数时间。因此有些子问题被重复计算了许多次。

如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

为了达到此目的，可以用一个表来记录所有已解决的子问题的答案

动态规划方法基本步骤

  1. 找出最优解的性质，并刻划其结构特征（最优子结构性质）。

  2. n递归地定义最优值。

  3. n以自底向上的方式计算出最优值。

  4. 根据计算最优值时得到的信息，构造最优解。

动态规划的两种等价的实现方法是什么，及其比较

第一种方法称为带备忘的自顶向下法。此方法仍按照自然的递归形式编写过程，但过程会保存每个子问题的解（通常是数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题。

第二种方法称为自底向上法。这种方法一般需要恰当定义子问题“规模”的概念，使得任何子问题的求解都只依赖于“更小的”子问题的求解。因而我们可以将子问题按规模排序，按由小到大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子问题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它时，它的所有前提子问题都已求解完成。

两种方法得到的算法都具有相同的渐近时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归考察所有可能的子问题。

由于没有频繁的递归函数调用的开销，自底向上方法的时间函数通常具有更小的系数。

动态规划算法的基本要素

  1. 最优子结构: 原问题的最优解包含着其子问题的最优解。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
  2. 重叠子问题:递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

动态规划方法发掘最优子结构的通用模式

  1. 证明问题最优解的第一个组成部分是做出一个选择，做出这次选择会产生一个或多个待解的子问题。
  2. 对于一个给定的问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。现在并不关心具体选择是如何得到的，只是假定已经知道了这种选择。
  3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻划子问题空间。
  4. 利用“剪切－粘贴”（cut-and-paste）技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

剪切－粘贴技术

假定子问题的解不是其自身的最优解，那么我们就可以从原问题的解中“剪切”掉这些非最优解，将最优解“粘贴”进去，从而得到原问题一个更优的解，这与最初的解是原问题的最优解的前提假设矛盾。如果原问题的最优解包含多个子问题，通常他们都很相似，我们可以将针对一个子问题的“剪切－粘贴”论证方法稍加修改，用于其他子问题。

矩阵连乘问题(homework)

题目大意

现在我们有n个矩阵，然后由于不同的先后计算次序会导致计算量不同，这个问题就是想找出使计算复杂最小的总数乘次数以及相应的方案。输入的p数组共有n+1个元素，也就是第i个矩阵是一个p[i-1] * p[i]这样大小的矩阵

实现思路

这里的关键在于，我们对Ai–Aj的这j-i+1个矩阵的最小次数问题转换为找到一个最优的二分点，使得对于这个二分点，左右部分内部最优值加上将两部分合并所需的计算花费最优。也就是在转移过程中不断将区间分割，从小区间最优一步步合并到大区间最优直到解决问题。在解决的过程中同时保存区间最优值情况时的分割点，以便于再利用向上回溯的方式重现处计算的顺序。

实现细节

可以利用记忆化的思想进行剪枝以大幅优化时间复杂度。还有要注意的是输入的是比矩阵数多一个，因为输入的是系数。另外就是一个数学知识：对于两个区段的矩阵相乘，计算总量是左边的行数乘左边列数乘右边列数，这个其实不难证明，但若没有接触过可能不是很容易想到。

递归实现代码

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
54
55
56
57
58
59
60
61
62
//
//  4th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//      Matrix problem using recursive algorithm. It's simple but poor in its performance cause their exists lots of repeated calculation.
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/26.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

int p[1010];
int s[1010][1010];

int re_matrix(int head,int tail)
{
    if (head >= tail)
        return 0;
    int ret = INF;
    int tep;
    for(int i=head;i<tail;i++)
    {
        tep = re_matrix(head, i) + re_matrix(i+1, tail) + p[head-1]*p[i]*p[tail];
        if (tep<ret)
        {
            s[head][tail] = i;
            ret = tep;
        }
    }
    return ret;
}
void Output_Ans(int head, int tail)
{
    if (head >= tail)
        return;
    Output_Ans(head, s[head][tail]);
    Output_Ans(s[head][tail]+1, tail);
    cout << "A" << head << "-" << s[head][tail];
    cout << " * A" << s[head][tail]+1 << "-" << tail << endl;
}

int main()
{
    int n;
    cout << "How many matrix?: ";
    cin >> n;
    for (int i=0;i<=n;i++)
        cin >> p[i];
    cout << "Min Time: " << re_matrix(1, n) << endl;
    Output_Ans(1, n);
}

动态规划实现代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//
//  4th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//      Matrix problem using dynamic programming. Manually cutting brunches makes it much more efficent than the formal one.
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/26.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

int p[1010];
int s[1010][1010];
int m[1010][1010];

int dp_matrix(int n)
{
    for (int i=0;i<=n;i++)
        m[i][i]=0;
    for (int len = 2;len<=n;len++)
        for (int head = 1;head<=n-len+1;head++)
        {
            int tail = head+len-1;
            m[head][tail] = INF;
            int tep;
            for (int i=head;i<tail;i++)
            {
                tep = m[head][i] + m[i+1][tail] + p[head-1]*p[i]*p[tail];
                if (tep < m[head][tail])
                {
                    m[head][tail] = tep;
                    s[head][tail] = i;
                }
            }
        }
    return m[1][n];
}
void Output_Ans(int head, int tail)
{
    if (head >= tail)
        return;
    Output_Ans(head, s[head][tail]);
    Output_Ans(s[head][tail]+1, tail);
    cout << "A" << head << "-" << s[head][tail];
    cout << " * A" << s[head][tail]+1 << "-" << tail << endl;
}

int main()
{
    int n;
    cout << "How many matrix?: ";
    cin >> n;
    for (int i=0;i<=n;i++)
        cin >> p[i];
    cout << "Min Time: " << dp_matrix(n) << endl;
    Output_Ans(1, n);
}

记忆化搜索实现代码

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
54
55
56
57
58
59
60
61
62
63
64
65
66
//
//  4th homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Introduction:
//      Matrix problem using memorized search. In fact, memorized search can replace dp in almost all problems.
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/26.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

int p[1010];
int s[1010][1010];
int m[1010][1010];

int dfs_matrix(int head,int tail)
{
    if (head >= tail)
        return 0;
    if (m[head][tail]!=0)
        return m[head][tail];
    m[head][tail] = INF;
    int tep;
    for(int i=head;i<tail;i++)
    {
        tep = dfs_matrix(head, i) + dfs_matrix(i+1, tail) + p[head-1]*p[i]*p[tail];
        if (tep<m[head][tail])
        {
            s[head][tail] = i;
            m[head][tail] = tep;
        }
    }
    return m[head][tail];
}
void Output_Ans(int head, int tail)
{
    if (head >= tail)
        return;
    Output_Ans(head, s[head][tail]);
    Output_Ans(s[head][tail]+1, tail);
    cout << "A" << head << "-" << s[head][tail];
    cout << " * A" << s[head][tail]+1 << "-" << tail << endl;
}

int main()
{
    int n;
    cout << "How many matrix?: ";
    cin >> n;
    for (int i=0;i<=n;i++)
        cin >> p[i];
    fulset(m, 0);
    cout << "Min Time: " << dfs_matrix(1, n) << endl;
    Output_Ans(1, n);
}

三者的输入输出

1
2
3
input:
6
30 35 15 5 10 20 25
1
2
3
4
5
6
7
output:
Min Time: 15125
A2-2 * A3-3
A1-1 * A2-3
A4-4 * A5-5
A4-5 * A6-6
A1-3 * A4-6

数字三角形问题(programming)

Author: YihangBao
Link: https://roarboil.github.io/2020/03/28/cha3-1/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.