【算法】动态规划
目录
- 动态规划总结
- 1、常见动态规划
- Fibonacci数列
- 杨辉三角
- 最小花费爬楼梯
- 孩子们的游戏
- 2、组合方案
- 李白打酒加强版（lqb）
- 3、背包问题
- 4、最长公共子序列
- 5、最长递增子序列
动态规划总结
动态规划通过将问题分解为子问题并存储子问题的解（由记忆化搜索延伸）来避免重复计算。动态规划的关键就是状态和转移。
- 特点：
- 重叠子问题：问题可以分解为多个重复的子问题，通过存储子问题的解避免重复计算；
- 最优子结构：问题的最优解可以通过子问题的最优解推导出来；
- 状态转移方程：通过方程描述问题状态之间的关系，定义如何从子问题的解推导出当前问题的解；
- 存储中间结果：通常使用数组或表格存储子问题的解，以便后续使用。
- 适用题型：
- 最优化问题：如最短路径、最长公共子序列等；
- 计数问题：如计算路径数量、组合数等；
- 组合问题：如背包问题、硬币找零等；
- 序列问题：如最长递增子序列、编辑距离等；
- 解题步骤：
- 定义状态：明确问题的状态表示；
- 确定状态转移方程：找出状态之间的关系；
- 初始化：设置初始状态的值；
- 计算顺序：确定计算状态的顺序，通常自底向上或自顶向下；
- 返回结果：根据存储的状态得到最终解。
以上内容由Deepseek和我共同总结。
动态规划的特点：
有后效性，当前的决策会影响到后面的决策。
具有最优子结构的特征。
解这类题的步骤：
-
定义数组（数学归纳法中的定义函数）：如f[i]表示的是什么，时刻记住你定义的数组的含义。有时题上为了降低难度会帮我们定义。但是有时也会误导我们。方案dp。
-
写状态转移方程。
有两种写法：f[i]由什么转移过来。f[i]可以发展到f[i+1]的什么情况。
通常我们写第一种写法，因为方便表达和下标的书写，理解起来更容易。 -
初始化。
初始化f[0]，初始化的方法有两种：根据定义的函数来写，根据实际意思。 -
枚举遍历所有的情况。用子结构递推到最终的结果。
以上是博主@一只蓝色小鲨鱼的总结，原文链接：动态规划——方案dp（考研复试上机知识点）。
1、常见动态规划
Fibonacci数列
Fibonacci数列
动态规划做法：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> dp(sqrt(n));
dp[0] = 0, dp[1] = 1;
int s1 = 0, s2 = 0;
for (int i = 2; i < n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
if (dp[i] > n)
{
while (dp[i] != n)
{
s1++;
dp[i]--;
}
while (dp[i - 1] != n)
{
s2++;
dp[i - 1]++;
}
break;
}
}
cout << min(s1, s2) << endl;
return 0;
}
滚动数组做法：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a = 0, b = 1, c = 1;
while (true)
{
if (c >= n) break;
a = b;
b = c;
c = a + b; // 这几个顺序不能乱，c = a + b最后算
}
cout << min((c - n), (n - b)) << endl;
return 0;
}
杨辉三角
杨辉三角
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(n, 1));
for (int y = 0; y < n; y++)
{
for (int x = 0; x < y + 1; x++)
{
if (y > 1)
{
if (x > 0 && x < y)
v[x][y] = v[x][y - 1] + v[x - 1][y - 1];
}
printf("%5d", v[x][y]);
}
cout << endl;
}
return 0;
}
最小花费爬楼梯
NC296 最小花费爬楼梯
- 注意要爬到楼顶，最后一个数之后才是楼顶，所以dp数组要多开一个空间。
下面的dp[i]表示到第i个台阶所花费的钱。 因此到楼顶就是dp[n]。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++)
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
return dp[n];
}
};
下面的dp[i]表示从第i个台阶到楼顶所花费的钱。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[n - 1] = cost[n - 1];
dp[n - 2] = cost[n - 2];
for (int i = n - 3; i >= 0; i--)
dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
return min(dp[0], dp[1]);
}
};
孩子们的游戏
- 孩子们的游戏
经典的约瑟夫环问题，也可以利用链表和数组模拟来做。本题通过动态规划可以找到一个规律。
其中 dp[i] 表示 i 个孩子的时候谁拿到了那个礼物。
class Solution {
public:
int LastRemaining_Solution(int n, int m) {
int f = 0; // 第一个孩子拿到礼物的就死他自己
for (int i = 2; i <= n; i++)
f = (f + m) % i;
return f;
}
};
2、组合方案
李白打酒加强版（lqb）
- 一般求合法的个数、顺序、排列、方案等且范围不是很大，大概率是用动态规划做。
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
// dp[i][j][k]表示经过i家店，j朵花，壶里还有k斗酒的方案总数
int dp[110][110][110];
int main()
{
int n, m;
cin >> n >> m;
dp[0][0][2] = 1;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
for (int k = 0; k < m; k++)
{
if (k % 2 == 0 && i > 0)
{
dp[i][j][k] += (dp[i - 1][j][k / 2]) % mod;
}
if (j > 0)
{
dp[i][j][k] += (dp[i][j - 1][k + 1]) % mod;
}
}
}
}
cout << dp[n][m - 1][1] << endl;
return 0;
}
3、背包问题
4、最长公共子序列
5、最长递增子序列
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
