网站导航
> 技术文档 > 算法基础--动态规划系列训练_记忆化递归 csdn

算法基础--动态规划系列训练_记忆化递归 csdn

网友: 技术文档 2025-07-30 13:00:01

1.记忆化搜索 在搜索的过程中，如果搜索树中有很多重复的结点，此时可以通过⼀个 \"备忘录\"，记录第⼀次搜索到的结果。当下⼀次搜索到这个结点时，直接在 \"备忘录\" ⾥⾯找结果。其中，搜索树中的⼀个⼀个结点，也称为⼀个⼀个状态。

2.递归改递推：

在⽤记忆化搜索解决斐波那契问题时，如果关注 \"备忘录\" 的填写过程，会发现它是从左往右依次填写 的。当 位置前⾯的格⼦填写完毕之后，就可以根据格⼦⾥⾯的值计算出 位置的值。所以，整个 递归过程，我们也可以改写成循环的形式，也就是递推：

3.动态规划

动态规划（Dynamic Programming，简称DP）是⼀种⽤于解决多阶段决策问题的算法思想。它通过 将复杂问题分解为更⼩的⼦问题，并存储⼦问题的解（通常称为“状态”），从⽽避免重复计算，提 ⾼效率。因此，动态规划⾥，蕴含着分治与剪枝思想。

注意： • 动态规划中的相关概念其实远不⽌如此，还会有：重叠⼦问题、最优⼦结构、⽆后效性、有向⽆ 环图等等。

4.如何利⽤动态规划解决问题

第⼀种⽅式当然就是记忆化搜索了： • 先⽤递归的思想去解决问题； • 如果有重复⼦问题，就改成记忆化搜索的形式。

第⼆种⽅式，直接使⽤递推形式的动态规划解决：

  1. 定义状态表示： ⼀般情况下根据经验+递归函数的意义，赋予 dp 数组相应的含义。（其实还可以去蒙⼀个，如果 蒙的状态表⽰能解决问题，说明蒙对了。如果蒙错了，再换⼀个试~）

  2. 推导状态转移⽅程： 根据状态表⽰以及题意，在 dp 表中分析，当前格⼦如何通过其余格⼦推导出来。

  3. 初始化：根据题意，先将显⽽易⻅的以及边界情况下的位置填上值。

  4. 确定填表顺序：根据状态转移⽅程，确定按照什么顺序来填表。

  5. 确定最终结果

动态规划以练习为主，从题中感受，再而自成体系，慢慢感悟

线性dp:

线性dp 是动态规划问题中最基础、最常见的⼀类问题。它的特点是状态转移只依赖于前一个或前几个
状态，状态之间的关系是线性的，通常可以用一维或者⼆维数组来存储状态。

背包问题：

状态表示—>状态转移方程—>初始化—>填表顺序              

01背包：

【模板】01背包

P1048 [NOIP 2005 普及组] 采药

P1164 小A点菜

P2946 [USACO09MAR] Cow Frisbee Team S

const int N = 1010; //https://ac.nowcoder.com/acm/problem/226514 【模板】01背包int n,m;int v[N], w[N];int f[N][N];//int dp[N][N]int main(){cin >> n >> m;for (int i = 1; i > v[i] >> w[i];//第一问）求这个背包至多能装多大价值的物品？for (int i = 1; i <= n; i++){for (int j = 1; j = 0)f[i][j] = max(f[i][j], w[i] + f[i-1][j - v[i]]);}}cout << f[n][m] << endl;//第二问 若背包恰好装满，求至多能装多大价值的物品？memset(f, -1, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j = 0&& f[i - 1][j - v[i]]>=0)f[i][j] = max(f[i][j], w[i] + f[i - 1][j - v[i]]);}}if (f[n][m] >= 0)cout << f[n][m] << endl;else cout << 0 <> n >> m;for (int i = 1; i > v[i] >> w[i];//第一问）求这个背包至多能装多大价值的物品？for (int i = 1; i = v[i]; j--){//f[j] = f[i - 1][j];if (j - v[i] >= 0)f[j] = max(f[j], w[i] + f[j - v[i]]);}}cout << f[m] << endl;//第二问 若背包恰好装满，求至多能装多大价值的物品？memset(f, -1, sizeof f);f[0] = 0;for (int i = 1; i = v[i]; j--){if (f[j - v[i]] >= 0)f[j] = max(f[j], w[i] + f[j - v[i]]);}}if (f[m] >= 0)cout << f[m] << endl;else cout << 0 << endl;}
const int N = 110, M = 1010; //https://www.luogu.com.cn/problem/P1048 P1048 [NOIP 2005 普及组] 采药int f[N][M];int t[N], w[N];int n, m;int main(){cin >> m >> n;for (int i = 1; i > t[i] >> w[i];for (int i = 1; i <= n; i++){for (int j = 0; j = t[i])f[i][j] = max(f[i][j], w[i] + f[i - 1][j - t[i]]);}}cout << f[n][m] << endl;}
const int N = 110, M = 1e4 + 10; //https://www.luogu.com.cn/problem/P1164 P1164 小A点菜int f[N][M]; //可以空间优化int n, m;int a[N];int main(){cin >> n >> m;for (int i = 1; i > a[i];f[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = 0; j = 0)f[i][j] += f[i-1][j - a[i]];//选的前提是 能选}}cout << f[n][m] << endl;}
const int N = 2010, M = 1010,mod=1e8; //https://www.luogu.com.cn/problem/P2946 P2946 [USACO09MAR] Cow Frisbee Team Sint w[N];int f[N][M];int n,m;int main(){cin >> n>>m;for (int i = 1; i > w[i];f[0][0] = 1;for (int i = 1; i <= n; i++){for (int j = 0; j < m; j++){f[i][j] = (f[i][j] + f[i - 1][j])%mod;f[i][j] = (f[i][j] + f[i - 1][((j - w[i]) % m + m) % m])%mod;}}cout << f[n][0] - 1 << endl;}

完全背包：

【模板】完全背包

P1616 疯狂的采药

 P2918 [USACO08NOV] Buying Hay S

P5662 [CSP-J2019] 纪念品

const int N = 1010; //https://ac.nowcoder.com/acm/problem/226516 【模板】完全背包int v[N], w[N];int f[N]; //空间优化后的代码int n, m;int main(){cin >> n >> m;for (int i = 1; i > v[i] >> w[i];for (int i = 1; i <= n; i++){for (int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m] << endl;memset(f, -0x3f3f, sizeof f);f[0] = 0;for (int i = 1; i <= n; i++){for (int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j - v[i]] + w[i]);}}if (f[m] < 0)cout << 0 << endl;else cout << f[m] << endl;}
const int N = 1e4+10, M = 1e7 + 10; //https://www.luogu.com.cn/problem/P1616 P1616 疯狂的采药typedef long long LL;LL f[M];int t[N], w[N];int n, m;int main(){cin >> m >> n;for (int i = 1; i > t[i] >> w[i];for (int i = 1; i <= n; i++){for (int j = t[i]; j <= m; j++){f[j] = max(f[j], f[j - t[i]] + w[i]);}}cout << f[m] << endl;}
#include //https://www.luogu.com.cn/problem/P2918 P2918 [USACO08NOV] Buying Hay S #include // 此题特殊在于求---------至少-------------------using namespace std;const int N = 110, M = 5e4 + 10;int f[N][M];int p[N], c[N];int n, m;int main(){cin >> n >> m;for (int i = 1; i > p[i] >> c[i];memset(f, 0x3f, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){f[i][j] = min(f[i - 1][j], f[i][max(0, j - p[i])] + c[i]);}}cout << f[n][m] <> n >> m;for (int i = 1; i > p[i] >> c[i];memset(f, 0x3f, sizeof f);f[0] = 0;for (int i = 1; i <= n; i++){for (int j = 0; j <= m; j++){f[j] = min(f[j], f[max(0, j - p[i])] + c[i]);}}cout << f[m] << endl;return 0;}
const int N=110, M = 1e4 + 10; //https://www.luogu.com.cn/problem/P5662 P5662 [CSP-J2019] 纪念品int f[M];int t, n, m;int a[N][N];int solve(int x, int y, int m){memset(f, 0, sizeof f); //多次调用一定要记得初始化for (int i = 1; i <= n; i++){for (int j = a[x][i]; j <= m; j++){f[j] = max(f[j], f[j - a[x][i]] + a[y][i] - a[x][i]);}}if (f[m] > t >> n >> m;for (int i = 1; i <= t; i++)for (int j = 1; j > a[i][j];for (int i = 1; i < t; i++) //拆分为计算每两天后的最大值{m=solve(i, i + 1, m);}cout << m << endl;}

多重背包：（两类解法）

多重背包

第一种解法：
const int N = 110; //https://ac.nowcoder.com/acm/problem/235950 多重背包int f[N][N];int n, m;int x[N], w[N], v[N];//个数 重量 价值int main(){cin >> n >> m;for (int i = 1; i > x[i] >> w[i] >> v[i];for (int i = 1; i <= n; i++){for (int j = 0; j = 0 && k <= x[i]; k++) //两大限制条件：取值限制和个数限制{f[i][j] = max(f[i][j], f[i - 1][j - k * w[i]] + k * v[i]);}}}cout << f[n][m] <> n >> m;for (int i = 1; i > x[i] >> w[i] >> v[i];for (int i = 1; i = 0; j--) //注意是逆序{for (int k = 0; j - k * w[i] >= 0 && k <= x[i]; k++){f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);}}}cout << f[m] << endl;}
第二种解法：（多重背包二进制优化后拆解为01背包）

注意：至于集合加入余数r（r>=0&&r<2^k）后证明能取到区间【2^k,m】，
可看做r+x(x属于【2^k  -r, 2^k  -1】),这显然成立，因为前面已经证明了x能取到【0，2^k  -1】.

 

采用二进制优化（多重背包-- > 01背包）时间复杂度O（n * m * logk）const int N = 110; // https://ac.nowcoder.com/acm/problem/235950 多重背包int f[5 * N];//每种背包个数最大为20，2^5-1=31>20int w[5 * N], v[5 * N];int n, m,pos;int main(){cin >> n >> m;//初始化时将前其按照二进制拆分，例如：9-->1 2 4 2 (分装成01背包，选或不选即可满足从0到9所有情况)for (int i = 1; i > x >> y >> z;int t = 1;while (x-t>0){++pos;w[pos] = t * y;v[pos] = t * z;x -= t;  //至关重要t *= 2;}if (x){++pos; //共有pos个w[pos] = x * y;v[pos] = x * z;}}for (int i = 1; i = w[i]; j--){f[j] = max(f[j], f[j - w[i]]+v[i]);}}cout << f[m] << endl;}
特殊： 计算方案数（不能二进制优化，会多次计算重复）

P1077 [NOIP 2012 普及组] 摆花

const int N = 110,mod=1e6+7; //https://www.luogu.com.cn/problem/P1077 P1077 [NOIP 2012 普及组] 摆花int n, m;int a[N];int f[N];int main(){cin >> n >> m;for (int i = 1; i > a[i];f[0] = 1;for (int i = 1; i = 0; j--){for (int k = 1; j - k >= 0 && k <= a[i]; k++){f[j] += f[j - k];f[j] %= mod;}}}cout << f[m] << endl;}

分组背包：

P1757 通天之分组背包

const int N = 1010; //https://www.luogu.com.cn/problem/P1757 P1757 通天之分组背包typedef pair PII;vectorg[N];int f[N];int n, m,cnt;int main(){cin >> m >> n;for (int i = 1; i > a >> b >> c;cnt = max(cnt, c);g[c].push_back({ a,b });}for (int i = 1; i = 0; j--){for (auto& t : g[i]){int x = t.first, y = t.second;if (j - x >= 0){f[j] = max(f[j],f[j - x] + y);}}}}cout << f[m] << endl;}

P5322 [BJOI2019] 排兵布阵

const int N = 110, M = 2e4 + 10; //https://www.luogu.com.cn/problem/P5322 P5322 [BJOI2019] 排兵布阵int a[N][N]; //城堡、组数int f[M]; //城堡、人数限制int s, n, m;int main(){cin >> s >> n >> m;for (int i = 1; i <= s; i++){for (int j = 1; j > a[j][i];a[j][i] = a[j][i] * 2 + 1;}}for(int i=1;i<=n;i++)sort(a[i] + 1, a[i] + s + 1);for (int i = 1; i =0; j--){//f[i][j] = f[i - 1][j];for (int k = 1; j - a[i][k] >= 0 && k <= s; k++){f[j] = max(f[j], f[j - a[i][k] ]+ k * i);}}}cout << f[m] << endl;}

混合背包：

P1833 樱花

const int N = 1e4 + 10,M=1010; //https://www.luogu.com.cn/problem/P1833 P1833 樱花int f[M];int t[N], c[N], p[N];int n, m;int main(){int t1, t2, t3, t4; char c1, c2;cin >> t2 >> c1 >> t1 >> t4 >> c2 >> t3>>n;m = (t4 - t2) * 60 + t3 - t1;for (int i = 1; i > t[i] >> c[i] >> p[i];for (int i = 1; i <= n; i++){if (p[i] == 0)//完全背包 从左到右{for (int j = t[i]; j = t[i]; j--){f[j] = max(f[j], f[j - t[i]] + c[i]);}}else //多重背包 从右到左{for (int j = m; j >= t[i]; j--){for (int k = 1; j - k * t[i] >= 0 && k <= p[i]; k++){f[j] = max(f[j], f[j - k * t[i]] + k * c[i]);}}}}cout << f[m] << endl;}

多维费用的背包问题：

P1910 L 国的战斗之间谍

const int N = 1010; //https://www.luogu.com.cn/problem/P1910 P1910 L 国的战斗之间谍int f[N][N];//能力 费用int n, m, x;int a[N], b[N], c[N];int main(){cin >> n >> m >> x;for (int i = 1; i > a[i] >> b[i] >> c[i];for (int i = 1; i = b[i]; j--){for (int k = x; k >= c[i]; k--){f[j][k] = max(f[j][k], f[j - b[i]][k - c[i]]+a[i]);}}}cout << f[m][x] << endl;return 0;}

区间dp：

P1435 [IOI 2000] 回文字串

const int N = 1010; //https://www.luogu.com.cn/problem/P1435 P1435 [IOI 2000] 回文字串int f[N][N]; //左端点、右端点string s;int main(){cin >> s;int len = s.size();s = \" \" + s;//若枚举左右端点得从下到上，从左到右还得不少判断。故而区间dp枚举的是长度和左端点（即从对角线斜着来）for (int i = 2; i <= len; i++)//先枚举长度 {for (int j = 1; j + i - 1 <= len; j++)//再枚举左端点{int right = j + i - 1;int left = j;if (s[left] == s[right])f[left][right] = f[left + 1][right - 1];else f[left][right] = min(f[left + 1][right] + 1, f[left][right - 1] + 1);}}cout << f[1][len] << endl;return 0;}

 P2858 [USACO06FEB] Treats for the Cows G/S

const int N = 2010;//https://www.luogu.com.cn/problem/P2858 P2858 [USACO06FEB] Treats for the Cows G/Sint f[N][N];int a[N];int n;int main(){cin >> n;for (int i = 1; i > a[i];for (int len = 1; len <= n; len++){for (int left = 1; left + len - 1<=n; left++){int right = left + len - 1;f[left][right] = max(f[left + 1][right] + a[left] * (n - len + 1), f[left][right - 1] + a[right] * (n - len + 1));}}cout << f[1][n] << endl;}

 P1775 石子合并（弱化版）

const int N = 310; //https://www.luogu.com.cn/problem/P1775 P1775 石子合并（弱化版）int sum[N];//前缀和int f[N][N];int n;int main(){cin >> n;for (int i = 1; i > tmp;sum[i] = sum[i - 1] + tmp;}for (int len = 2; len <= n; len++){for (int left = 1; left + len - 1 <= n; left++){int right = left + len - 1;f[left][right] = f[left][left] + f[left + 1][right] + sum[right] - sum[left - 1]; //先赋一个值，应为后续要min（此处类同于k=left）for (int k = left + 1; k < right; k++){f[left][right] = min(f[left][right], f[left][k] + f[k + 1][right] + sum[right] - sum[left - 1]);}}}cout << f[1][n] << endl;}

采用倍增数组来解决下述环问题 P1880 [NOI1995] 石子合并

const int N = 210; //https://www.luogu.com.cn/problem/P1880 P1880 [NOI1995] 石子合并int n;int sum[N];int f[N][N];int g[N][N];int main(){cin >> n;//倍增数组for (int i = 1; i > t;sum[i] = t;sum[i + n] = t;}for (int i = 1; i <= 2 * n; i++)sum[i] = sum[i] + sum[i - 1];for (int len = 2; len <= n; len++){for (int left = 1; left + len - 1 <=2*n; left++){int right = left + len - 1;f[left][right] = f[left][left] + f[left + 1][right] + sum[right] - sum[left - 1];g[left][right] = g[left][left] + g[left + 1][right] + sum[right] - sum[left - 1];for (int k = left + 1; k < right; k++){f[left][right] = min(f[left][right], f[left][k] + f[k+1][right] + sum[right] - sum[left - 1]);g[left][right] = max(g[left][right], g[left][k] + g[k+1][right] + sum[right] - sum[left - 1]);}}}int ret = f[1][n]; int ret2 = g[1][n];for (int i = 2; i <= n; i++){ret = min(ret, f[i][i + n-1]);ret2 = max(ret2, g[i][i + n - 1]);}cout << ret << endl;cout << ret2 << endl;}

 P3146 [USACO16OPEN] 248 G（对于合并有外加限制条件）

const int N = 260; //https://www.luogu.com.cn/problem/P3146 P3146 [USACO16OPEN] 248 Gint f[N][N];//f[i][j]严格存储的是i-j合并为一个数后的值，没有就为0int a[N];int n, ret;int main(){cin >> n;for (int i = 1; i > a[i];f[i][i] = a[i];ret = max(ret, a[i]);}for (int len = 2; len <= n; len++){for (int left = 1; left + len - 1 <= n; left++){int right = left + len - 1;for (int k = left; k < right; k++){if (f[left][k] == f[k + 1][right]&&f[left][k]!=0)f[left][right] = max(f[left][right],f[left][k] + 1);}ret = max(ret, f[left][right]);}}cout << ret << endl;}

本人后续在复习时会对本篇文章代码所对应的题目做尽量详细的剖解

网络标签：

相关问题