抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

动态规划学习笔记

算法学习

发布于：2023年1月7日

本篇博客为一些动态规划学习的笔记。

前言

一个问题能用动态规划解决需要满足三个条件：有边界条件、有递推方程且具有最优子结构性质。

递推地求解斐波那契数列是最朴素的动态规划问题之一，下面三个函数的求解效率从上到下依次递增。

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

// 0 <= n <= 25
const int N = 30;

int n, mem[N];

// 朴素的暴力搜索
int fib_by_dfs(int n) {
	if (n == 0 || n == 1) return 1;
	else return fib_by_dfs(n - 1) + fib_by_dfs(n - 2);
}

// 记忆化搜索
int fib_by_dfs_mem_opt(int n) {
	if (~mem[n]) return mem[n];
	else return mem[n] = (mem[n - 1] = fib_by_dfs(n - 1)) +
		(mem[n - 2] = fib_by_dfs(n - 2));
}

// 动态规划
int fib_by_dp_opt(int n) {
	int dp[N];
	dp[0] = 1, dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}

int main() {
	int n;
	cin >> n;
	// 将备忘录数组初始化为不在计算过程出现的数据即可，这里选用-1
	memset(mem, -1, sizeof mem);
	cout << fib_by_dp_opt(n) << endl;
	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
#include <iostream>
using namespace std;

const int N = 104;

int g[N][N], n;

// 朴素的暴力搜索算法，没有任何优化，有重复枚举需要重新计算
int dfs(int x, int y) {
    if(x == n && y == n) return g[n][n];
    if(x > n || y > n) return 1e9;
    return min(dfs(x + 1, y), dfs(x, y + 1)) + g[x][y];
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }
    cout << dfs(1, 1) << endl;
    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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 104;

int g[N][N], n;
int f[N][N];

// 记忆化搜索优化，用-1代表位置并未被搜索过，减少大量不必要的重复计算后代码不会TLE
int dfs(int x, int y) {
    if(~f[x][y]) return f[x][y];
    if(x == n && y == n) return g[n][n];
    if(x > n || y > n) return 1e9;
    return f[x][y] =  min(f[x + 1][y] = dfs(x + 1, y),
					      f[x][y + 1] = dfs(x, y + 1)) + g[x][y];
}

int main() {
    memset(f, -1, sizeof f);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }
    cout << dfs(1, 1) << endl;
    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
#include <iostream>
#include <cstring>
using namespace std;

const int N = 103;

int n;
int g[N][N], dp[N][N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }   
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
			// 注意边界条件
            if(i == 1 && j == 1) dp[i][j] = 0;
            else dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
            dp[i][j] += g[i][j];
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

明白以上原理后可以在AcWing算法提高课中进行进一步的练习。

其他示例代码

最大连续子序列之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define INF 10000009
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	int tmpSum = 0, maxSum = 0;
	for (auto i : nums) {
		tmpSum = max(tmpSum + i, i);
		maxSum = max(tmpSum, maxSum);
	}
	cout << maxSum << endl;
	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
#include<bits/stdc++.h>
#define INF 1000000009
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> mSize(n + 1);
	mSize[0] = pair<int, int>(-1, -1);
	for (int i = 1; i <= n; i++){
		cin >> mSize[i].first >> mSize[i].second;
	}
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= n; i++) {
		dp[i][i] = 0;
	}
	for (int len = 2; len <= n; len++) { //计算长度为len的矩阵链最优值
		for (int i = 1; i <= n - len + 1; i++) { //矩阵链的开始矩阵下标
			int j = i + len - 1;                    //矩阵链的结束矩阵下标
			for (int k = i; k < j; k++) {  //枚举划分位置
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + mSize[i].first * mSize[k].second * mSize[j].second);
			}
		}
	}
	cout << dp[1][n] << endl;
    /*测试数据
	6
	30 35 35 15 15 5 5 10 10 20 20 25
    ans:15125
	*/
	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
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {//集合划分
	int n;
	cin >> n;
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
	//dp[i][j]代表i个元素时划分为j个集合有多少种方法
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i >= j) {
				if (j == 1) {
					dp[i][j] = 1;
				}
				else {
					dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1];
				}
			}
		}
	}
	ll ans = 0;//注意结果是否溢出
	for (int i = 1; i <= n; i++) {
		ans += dp[n][i];
	}
	cout << ans << endl;
	return 0;
}

数字三角形模型

AcWing 1015

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
#include <bits/stdc++.h>
using namespace std;

const int N = 101;
const int dx[2] = {0, 1}, dy[2] = {1, 0};
int g[N][N], f[N][N];
int n, m;

void solve() {
    cin >> n >> m;
    memset(f, 0, sizeof f);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];
        }
    }
    cout << f[n][m] << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

AcWing 1018

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
#include <bits/stdc++.h>
using namespace std;

const int N = 101;

int g[N][N], dp[N][N];
int n;

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> g[i][j];
        }
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i = 0; i <= n; i++) dp[i][0] = dp[0][i] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i > 1 && j > 1) dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]);
            else if(i == 1) dp[i][j] = dp[i][j - 1];
            else dp[i][j] = dp[i - 1][j];
            dp[i][j] +=  g[i][j];
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

AcWing 1027

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
#include <bits/stdc++.h>
using namespace std;

// 符合题意的任何(1,1) -> (n,n)路径长度相同，所以可以同时走

const int N = 11;

int g[N][N], f[2 * N][N][N];
int n;

bool valid(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= n;
}

int main() {
    cin >> n;
    int a, b, c;
    while(cin >> a >> b >> c && (a + b + c)) {
        g[a][b] = c;
    }
    for(int len = 2; len <= 2 * n; len++) {
        for(int i1 = 1; i1 <= n; i1++) {
            for(int i2 = 1; i2 <= n; i2++) {
                int j1 = len - i1, j2 = len - i2;
                if(valid(j1, j2)) {
                    int t = g[i1][j1];
                    if(i1 != i2) t += g[i2][j2];
                    for(int i = 0; i < 4; i++) {
                        f[len][i1][i2] = max(f[len][i1][i2], f[len - 1][i1 -(i & 1)][i2 - ((i >> 1) & 1)] + t);
                    }
                }
            }
        }
    }
    cout << f[n * 2][n][n] << endl;
    return 0;
}

AcWing 275

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
#include <bits/stdc++.h>
using namespace std;

// 符合题意的任何(1,1) -> (n,m)路径长度相同，所以可以同时走

const int N = 55;

int g[N][N], f[2 * N][N][N];
int n, m;

bool valid(int y) {
    return y >= 1 && y <= m;
}

int main() {
    cin >> n >> m;
    int a, b, c;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    for(int len = 2; len <= m + n; len++) {
        for(int i1 = 1; i1 <= n; i1++) {
            for(int i2 = 1; i2 <= n; i2++) {
                int j1 = len - i1, j2 = len - i2;
                if(valid(j1) && valid(j2)) {
                    int t = g[i1][j1];
                    if(i1 != i2 || j1 != j2) t += g[i2][j2];
                    for(int i = 0; i < 4; i++) {
                        f[len][i1][i2] = max(f[len][i1][i2], f[len - 1][i1 -(i & 1)][i2 - ((i >> 1) & 1)] + t);
                    }
                }
            }
        }
    }
    cout << f[n + m][n][n] << endl;
    return 0;
}

最长上升子序列模型

AcWing 1017

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

const int N = 110;

int arr[N], dp_inc[N], dp_dec[N];
int ans = -1, n;

void solve() {
    ans = -1;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp_inc[i] = dp_dec[i] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(arr[i] > arr[j]) dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1);
            if(arr[i] < arr[j]) dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1);
        }
        ans = max(ans, max(dp_inc[i], dp_dec[i]));
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

AcWing 1014

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

const int N = 1010;

int arr[N], dp_inc[N], dp_dec[N], n;

int main() {
    int ans = -1;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp_inc[i] = dp_dec[i] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(arr[i] > arr[j]) dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1);
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int j = n; j > i; j--) {
            if(arr[i] > arr[j]) dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1);
        }
    }
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp_dec[i] + dp_inc[i] - 1);
    }
    cout << ans << endl;
    return 0;
}

AcWing 482

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

const int N = 1010;

int arr[N], dp_inc[N], dp_dec[N], n;

int main() {
    int ans = -1;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp_inc[i] = dp_dec[i] = 1;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < i; j++) {
            if(arr[i] > arr[j]) dp_inc[i] = max(dp_inc[i], dp_inc[j] + 1);
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int j = n; j > i; j--) {
            if(arr[i] > arr[j]) dp_dec[i] = max(dp_dec[i], dp_dec[j] + 1);
        }
    }
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp_dec[i] + dp_inc[i] - 1);
    }
    // compared to 1014, the only difference is the output
    cout << n - ans << endl;
    return 0;
}

背包模型

AcWing 423

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>

using namespace std;

#define MAX_N 101
#define MAX_V 1010

int costs[MAX_N], values[MAX_N], dp[MAX_V];

int main() {
    int v, n;
    cin >> v >> n;
    for(int i = 1; i <= n; i++) {
        cin >> costs[i] >> values[i];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = v; j >= costs[i]; j--) {
            dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);
        }
    }
    cout << dp[v] << endl;
    return 0;
}

评论