动态规划

动态规划的四种模型

解决动态规划问题的一般思路：先写出暴力“尝试”的方法（递归、人的自然智慧），然后基于暴力递归看是否右重复求解的情况来写出“傻缓存”的方法，最后尝试基于暴力递归写出动态优化的版本

从左向右的尝试模型

经典题型：斐波那契数列、走楼梯

范围尝试模型

经典题型：机器人走路（1~N的位置上）、马在棋盘上跳（棋盘大小为10*9）、01背包问题

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <vector>
using namespace std;

// 假设有排成一行的N个位置，记为1~N,N一定大于或等于2开始时机器人在其中的M位置上(M一定是1~N中的一个)
// 如果机器人来到1位置，那么下一步只能往右来到2位置﹔如果机器人来到N位置，那么下一步只能往左来到N-1位置;
// 如果机器人来到中间位置，那么下一步可以往左走或者往右走;
// 规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种给定四个参数N、M、K、P，返回方法数。


// 机器人当前来到的位置是cur,
// 机器人还有rest步需要去走,
// 最终的目标是aim,
// 有哪些位置?1~N
// 返回:机器人从cur出发,走过rest步之后,最终停在aim的方法数,是多少?
static int process1(int cur, int rest, int aim, int N)
{
    // base case
    if (rest == 0)
    {
        // 经过 rest 步之后最终到达 aim，则说明这是一次成功的暴力递归搜索到的方法
        return cur == aim ? 1 : 0;
    }
    // rest > 0 还剩有步数
    if (cur == 1)
    {
        // 1 -> 2
        return process1(2, rest - 1, aim, N);
    }
    if (cur == N)
    {
        // N-1 <- N
        return process1(N - 1, rest - 1, aim, N);
    }
    // 中间位置上
    return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
}
static int ways1(int N, int start, int aim, int K)
{
    if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 0)
    {
        return -1;
    }
    return process1(start, K, aim, N);
}

// cur的范围：1~N
// rest的范围：0~K
static int process2(int cur, int rest, int aim, int N, vector<vector<int>> &dp)
{
    if (dp[cur][rest] != -1)
    {
        return dp[cur][rest];
    }
    int ans = 0;
    if (rest == 0)
    {
        ans = cur == aim ? 1 : 0;
    }
    else if (cur == 1)
    {
        ans = process2(2, rest - 1, aim, N, dp);
    }
    else if (cur == N)
    {
        ans = process2(N - 1, rest - 1, aim, N, dp);
    }
    else
    {
        ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
    }
    dp[cur][rest] = ans;
    return ans;
}
// 缓存的方法: 确保了重复的过程只会进入一遍
static int ways2(int N, int start, int aim, int K)
{
    vector<vector<int>> dp(N + 1, vector<int>(K + 1, -1));
    return process2(start, K, aim, N, dp);
}

// 动态规划 状态转移矩阵
static int ways3(int N, int start, int aim, int K)
{
    vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
    dp[aim][0] = 1;

    for (int rest = 1; rest <= K; rest++)
    {
        // 当机器人来到边界位置的时候只依赖一个位置
        dp[1][rest] = dp[2][rest - 1];
        for (int cur = 2; cur < N; cur++)
        {
            // 当机器人来到中间的位置的时候依赖的是左右两个位置
            dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
        }
        dp[N][rest] = dp[N - 1][rest - 1];
    }
    // 最终要返回 start 位置开始走 K 步到 aim 的方法数
    return dp[start][K];
}

void test1()
{
    // 从 start 位置开始
    int start = 2;
    // 走 K 步
    int K = 6;
    // 目标位置是 aim
    int aim = 4;
    // 总共有 1~N 个位置
    int N = 5;
    cout << ways1(N, start, aim, K) << endl;
    cout << ways2(N, start, aim, K) << endl;
    cout << ways3(N, start, aim, K) << endl;
}

int main()
{
    test1();

    return 0;
}

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 给定长度都为N的数组weights和values，weights[i]values[i]分别代表
// i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子
// 你装的物品不能超过这个重量。返回你能装的最大价值是多少？
//

// i... 的货物自由选择，形成的最大价值返回
// 重量永远不要超过bag
// 之前做的决定，所达到的重量，alreadyweight
int process1(vector<int> &weights, vector<int> &values, int i, int alreadyweight, int bag)
{
    if (alreadyweight > bag)
    {
        return 0;
    }
    // 没有货物的最大价值当然为0
    if (i == weights.size())
    {
        return 0;
    }
    return max(process1(weights, values, i + 1, alreadyweight, bag),
               values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag));
}
// 另外一种暴力递归的写法
int process2(vector<int> &weights, vector<int> &values, int i, int alreadyWeight, int alreadyValue, int bag)
{
    if (alreadyWeight > bag)
        return 0;
    if (i == values.size())
        return alreadyValue;
    return max(process2(weights, values, i + 1, alreadyWeight, alreadyValue, bag),
               process2(weights, values, i + 1, alreadyWeight + weights[i], alreadyValue + values[i], bag));
}
int maxValue(vector<int> &weights, vector<int> &values, int bag)
{
    return process1(weights, values, 0, 0, bag);
}
void test1()
{
}

int main()
{

    return 0;
}

样本对应模型

经典题型：最长公共子序列、最长回文子序列

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

// 最长公共子序列

// str1[0...j] str2[0...j]最长公共子序列多长
// 返回
int process1(string &str1, string &str2, int i, int j)
{
    if (i == 0 && j == 0)
    {
        return str1[i] == str2[j] ? 1 : 0;
    }
    else if (i == 0)
    {
        if (str1[i] == str2[j])
            return 1;
        else
            return process1(str1, str2, i, j - 1);
    }
    else if (j == 0)
    {
        if (str1[i] == str2[j])
            return 1;
        else
            return process1(str1, str2, i - 1, j);
    }
    // i != 0 && j != 0
    else
    {
        // 考虑最长公共子序列以 str1[i] 结尾的情况
        int p1 = process1(str1, str2, i, j - 1);
        // 考虑最长公共子序列以 str2[j] 结尾的情况
        int p2 = process1(str1, str2, i - 1, j);
        // 最长公共子序列必须以 str1[i] 和 str2[j] 结尾，但是有这两个字符相等的前提
        int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
        return max(p1, max(p2, p3));
    }
}
int longestCommonSubsequence1(string &text1, string &text2)
{
    if (text1.size() == 0 || text2.size() == 0)
    {
        return 0;
    }
    return process1(text1, text2, text1.size() - 1, text2.size() - 1);
}

int longestCommonSubsequence2(string &text1, string &text2)
{
    if (text1.size() == 0 || text2.size() == 0)
    {
        return 0;
    }
    int N = text1.size();
    int M = text2.size();
    vector<vector<int>> dp(N, vector<int>(M, 0));
    dp[0][0] = text1[0] == text2[0] ? 1 : 0;
    for (int j = 1; j < M; j++)
    {
        dp[0][j] = text1[0] == text2[j] ? 1 : dp[0][j - 1];
    }
    for (int i = 1; i < N; i++)
    {
        dp[i][0] = text1[i] == text2[0] ? 1 : dp[i - 1][0];
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = 1; j < M; j++)
        {
            int p1 = dp[i - 1][j];
            int p2 = dp[i][j - 1];
            int p3 = text1[i] == text2[j] ? (1 + dp[i - 1][j - 1]) : 0;
            dp[i][j] = max(p1, max(p2, p3));
        }
    }
    return dp[N - 1][M - 1];
}

void test1()
{
    string text1 = "1a2a34a56";
    string text2 = "afdgafgfd123456dhasgfagfarug";
    cout << longestCommonSubsequence1(text1, text2) << endl;
    cout << longestCommonSubsequence2(text1, text2) << endl;
}

int main()
{
    test1();

    return 0;
}

业务限制模型

经典题型：咖啡杯问题

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 给定一个数组arr,arr[i]代表第i号咖啡机泡一杯咖啡的时间
// 给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡
// 只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
// 每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
// 假设所有人拿到咖啡之后立刻喝干净，
// 返回从开始等到所有咖啡机变干净的最短时间
// 三个参数:int[]arr、int N, int a、int b

class Machine
{
public:
    int timePoint;
    int workTime;
    Machine(int t, int w) : timePoint(t), workTime(w) {}
    bool operator<(const Machine &m1) const
    {
        return timePoint + workTime > m1.timePoint + m1.workTime;
    }
};
// drinks 所有杯子开始洗的时间；升序
// wash 单杯洗干净的时间（串行）
// air 挥发干净的时间（并行）
// free 洗咖啡杯的机器什么时候可用
// drinks[index ... ] 都变干净，最早的时间返回
static int bestTime(vector<int> &drinks, int wash, int air, int index, int free)
{
    if (index == drinks.size())
    {
        return 0;
    }
    // index 号杯子决定洗
    int selfClean1 = max(drinks[index], free) + wash;
    int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
    int p1 = max(selfClean1, restClean1);
    // index 号杯子决定挥发
    int selfClean2 = drinks[index] + air;
    int restClean2 = bestTime(drinks, wash, air, index + 1, free);
    int p2 = max(selfClean2, restClean2);
    return min(p1, p2);
}
static int bestTimeDp(vector<int> &drinks, int wash, int air)
{
    int N = drinks.size();
    int maxFree = 0;
    for (int i = 0; i < N; i++)
    {
        maxFree = max(maxFree, drinks[i]) + wash;
    }
    vector<vector<int>> dp(N + 1, vector<int>(maxFree + 1, 0));

    // dp[N][...] = 0;
    for (int index = N - 1; index >= 0; index--)
    {
        for (int free = 0; free <= maxFree; free++)
        {
            int selfClean1 = max(drinks[index], free) + wash;
            if (selfClean1 > maxFree)
            {
                continue;
            }
            int restClean1 = dp[index + 1][selfClean1];
            int p1 = max(selfClean1, restClean1);

            int selfClean2 = drinks[index] + air;
            int restClean2 = dp[index + 1][free];
            int p2 = max(selfClean2, restClean2);
            dp[index][free] = min(p1, p2);
        }
    }

    return dp[0][0];
}
int minTime1(vector<int> &arr, int n, int a, int b)
{
    priority_queue<Machine> heap;
    for (int i = 0; i < arr.size(); i++)
    {
        heap.push(Machine(0, arr[i]));
    }
    vector<int> drinks(n, 0);
    for (int i = 0; i < n; i++)
    {
        Machine cur = heap.top();
        heap.pop();
        cur.timePoint += cur.workTime;
        drinks[i] = cur.timePoint;
        heap.push(cur);
    }
    return bestTime(drinks, a, b, 0, 0);
    // return bestTimeDp(drinks, a, b);
}

void test1()
{
    priority_queue<Machine> heap;
    heap.push(Machine(0, 1));
    heap.push(Machine(0, 3));
    heap.push(Machine(0, 7));
    while (!heap.empty())
    {
        cout << heap.top().timePoint << " " << heap.top().workTime << endl;
        heap.pop();
    }
}

void test2()
{
    vector<int> arr = {1, 3, 7};
    int a = 3;
    int b = 4;
    int n = 20;
    cout << minTime1(arr, n, a, b) << endl;
}

int main()
{
    // test1();
    test2();

    return 0;
}
算法
#动态规划的四种模型
动态规划
http://example.com/2023/08/29/动态规划/
作者
WHC
发布于
2023年8月29日
许可协议