【算法】动态规划

ops/2025/3/19 7:00:50/
头像
⭐️个人主页：@小羊
⭐️所属专栏：Linux
很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

目录

  • 动态规划总结
    • 1、常见动态规划
      • Fibonacci数列
      • 杨辉三角
      • 最小花费爬楼梯
      • 孩子们的游戏
      • 不同路径
      • 不同路径II
      • 珠宝的最高价值
      • 下降路径最小和
      • 最小路径和
      • 地下城游戏（*）
    • 2、多状态dp
      • 面试题 17.16. 按摩师
    • 2、组合方案
      • 李白打酒加强版（lqb）
    • 3、背包问题
    • 4、最长公共子序列
    • 5、最长递增子序列

动态规划总结

动态规划通过将问题分解为子问题并存储子问题的解（由记忆化搜索延伸）来避免重复计算。动态规划的关键就是状态和转移。

  • 特点：
    1. 重叠子问题：问题可以分解为多个重复的子问题，通过存储子问题的解避免重复计算；
    2. 最优子结构：问题的最优解可以通过子问题的最优解推导出来；
    3. 状态转移方程：通过方程描述问题状态之间的关系，定义如何从子问题的解推导出当前问题的解；
    4. 存储中间结果：通常使用数组或表格存储子问题的解，以便后续使用。
  • 适用题型：
    1. 最优化问题：如最短路径、最长公共子序列等；
    2. 计数问题：如计算路径数量、组合数等；
    3. 组合问题：如背包问题、硬币找零等；
    4. 序列问题：如最长递增子序列、编辑距离等；
  • 解题步骤：
    1. 定义状态：明确问题的状态表示；
    2. 确定状态转移方程：找出状态之间的关系；
    3. 初始化：设置初始状态的值；
    4. 计算顺序：确定计算状态的顺序，通常自底向上或自顶向下；
    5. 返回结果：根据存储的状态得到最终解。

以上内容由Deepseek和我共同总结。

动态规划的特点：
有后效性，当前的决策会影响到后面的决策。
具有最优子结构的特征。

解这类题的步骤：

  1. 定义数组（数学归纳法中的定义函数）：如f[i]表示的是什么，时刻记住你定义的数组的含义。有时题上为了降低难度会帮我们定义。但是有时也会误导我们。方案dp。

  2. 写状态转移方程。
    有两种写法：f[i]由什么转移过来。f[i]可以发展到f[i+1]的什么情况。
    通常我们写第一种写法，因为方便表达和下标的书写，理解起来更容易。

  3. 初始化。
    初始化f[0]，初始化的方法有两种：根据定义的函数来写，根据实际意思。

  4. 枚举遍历所有的情况。用子结构递推到最终的结果。

以上是博主@一只蓝色小鲨鱼的总结，原文链接：动态规划——方案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;}
};

不同路径

  • 不同路径

在这里插入图片描述

这题之前用dfs（记忆化搜索）做过，不过还是用动态规划做更简单。这题唯一需要注意的是初始化，不同于一维dp，二维dp考虑的相对较多。

状态：dp[i][j] 表示到达 [i][j] 这个位置有多少种路径。
转移：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

在这里插入图片描述

class Solution {int dp[101][101];
public:int uniquePaths(int m, int n) {dp[0][1] = 1;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n];}
};

不同路径II

  • 不同路径II

在这里插入图片描述

和上题一样，就是多了一个障碍物，当遇到障碍物时不用递推就行，也就是不经过这个网格。
还有就是，我们多加了一行一列保证访问不会越界，所以我们的 dp 表和题给矩阵要正确映射。

class Solution {int dp[101][101];
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {dp[0][1] = 1;int m = obstacleGrid.size(), n = obstacleGrid[0].size();for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)if (obstacleGrid[i - 1][j - 1] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n];}
};

珠宝的最高价值

  • 珠宝的最高价值

在这里插入图片描述
这题我们也是多加了一行一列保证访问不会越界，所以 dp[i][j] 对应的应该是 frame[i - 1][j - 1]。

状态：dp[i][j] 表示到达 [i][j] 这个位置时拿到的所有珠宝的最大价值。
转移：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];。

class Solution {int dp[201][201];
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), n = frame[0].size();for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];return dp[m][n];}
};

下降路径最小和

  • 下降路径最小和

在这里插入图片描述

动态规划中初始化步骤不止为了保证不会越界，还为了保证结果的正确性。

二维 dp 表的初始化：
在这里插入图片描述

状态：dp[i][j] 表示到达 [i][j] 这个位置时下降路径最小和。
转移：dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1]。

最后需要返回到达最后一行的所有路径最小和中的最小值。

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n+1, vector<int>(n+2, INT_MAX));for (int i = 0; i <= n + 1; i++) dp[0][i] = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i-1][j+1])) + matrix[i-1][j-1];int ret = INT_MAX;for (int i = 1; i <= n; i++)ret = min(ret, dp[n][i]);return ret;}
};

最小路径和

  • 最小路径和

在这里插入图片描述

在这里插入图片描述

这道题和“珠宝的最高价值”类似，但是本题是求最小值，所以初始化的时候要特别注意。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));dp[0][1] = dp[1][0] = 0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];return dp[m][n];}
};

地下城游戏（*）

  • 地下城游戏

在这里插入图片描述

这道题和以往不同，不能以某个位置为结尾进行状态表示，只能以某个位置为起点表示状态。

状态：dp[i][j] 表示从 [i][j] 这个位置到终点健康点数的最小值。

从起点到终点的过程中，最小健康点数要么不变，要么减小，所以上一个位置的最小健康点数一定大于等于当前位置的最小健康点数，即 dp[i][j] + dungeon[i][j] >= dp[i + 1][j]，且要保证 dp[i][j] 不能小于1。

转移：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));dp[m][n - 1] = dp[m - 1][n] = 1;for (int i = m - 1; i >= 0; i--)for (int j = n - 1; j >= 0; j--){dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]); }return dp[0][0];}
};

2、多状态dp

面试题 17.16. 按摩师

  • 面试题 17.16. 按摩师

请添加图片描述

在这里插入图片描述

class Solution {
public:int massage(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;vector<int> f(n), g(n);f[0] = nums[0];for (int i = 1; i < n; i++){f[i] = g[i - 1] + nums[i];g[i] = max(f[i - 1], g[i - 1]);}return max(f[n - 1], g[n - 1]);}
};

2、组合方案

李白打酒加强版（lqb）

在这里插入图片描述
在这里插入图片描述
请添加图片描述

  • 一般求合法的个数、顺序、排列、方案等且范围不是很大，大概率是用动态规划做。

本题的关键所在是：最后一次遇到花，且酒恰好喝完。

动态规划的两大要素：状态和转移。
状态：题中共有三个状态：店、花、酒。所以设 dp[i][j][k] 表示经过i家店，j朵花，壶里还有k斗酒的方案数。
转移：假设李白的壶中此时有k斗酒，则此时的状态 dp[i][j][k] 可以由 dp[i-1][j][k/2] （上一次遇到的是店，但是需要注意此时的k必须是偶数，因为此时的k是由上一次遇到店翻倍而来）和 dp[i][j-1][k+1] （上一次遇到的是花）转移而来。

最后返回 dp[n][m-1][1]，因为要保证最后一次遇到的是花，且酒恰好还剩一斗。

#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、最长递增子序列

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

头像

http://www.ppmy.cn/ops/166970.html

相关文章

leetcode 3110. 字符串的分数 简单

leetcode 3110. 字符串的分数 简单

给你一个字符串 s 。一个字符串的 分数 定义为相邻字符 ASCII 码差值绝对值的和。 请你返回 s 的 分数 。 示例 1&#xff1a; 输入&#xff1a;s "hello" 输出&#xff1a;13 解释&#xff1a; s 中字符的 ASCII 码分别为&#xff1a;h 104 &#xff0c;e …
阅读更多...
SY6280AAC usb电流限流电子开关

SY6280AAC usb电流限流电子开关

电流设置图 电路原理图 参考链接 SY6280AAC -PDF数据手册-参考资料-立创商城https://item.szlcsc.com/datasheet/SY6280AAC/56162.html?spmsc.it.xds.a&lcsc_vidRgVaBABUQgdeAQZTR1FbUwBfRlEIVFNTEVlXXgFSTlAxVlNSRVNXVFBRRVZWVDsOAxUeFF5JWAIASQYPGQZABAsLWA%3D%3D 我做…
阅读更多...
C++学习之云盘项目nginx

C++学习之云盘项目nginx

1.复习 2.知识点概述 1. 一些基本概念 1.1 Nginx 初步认识 1.2 正向 / 反向代理 1.3 域名和 IP 2. Nginx 安装和配置 2.1 安装 2.2 配置 3. Nginx 的使用 3.1 部署静态网页 3.2 反向代理和负载均衡 课外知识导读 1. URL 和 URI 2. DNS 解析过程 1. 一些基…
阅读更多...
批量测试IP和域名联通性2

批量测试IP和域名联通性2

在前面批量测试IP和域名联通性-CSDN博客的基础上&#xff0c;由于IP和域名多样性&#xff0c;比如带端口号的192.168.1.17:17&#xff0c;实际上应该ping 192.168.1.17。如果封禁http://www.abc.com/a.exe&#xff0c;实际可ping www.abc.com。所以又完善了代码。 echo off se…
阅读更多...
【npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree】

【npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree】

npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree 当我们拿到一个前端项目的时候&#xff0c;想要把它运行起来&#xff0c;首先是要给它安装依赖&#xff0c;即cd到…
阅读更多...
Python 集合全面解析

Python 集合全面解析

一、集合核心特性 1. ​无序性与唯一性 ​无序性&#xff1a;集合中的元素没有固定顺序&#xff0c;无法通过索引访问。​唯一性&#xff1a;自动过滤重复元素&#xff0c;确保每个元素唯一。 unique_set {1, 2, 2, "苹果", "苹果"} # 输出&#xff1…
阅读更多...
数据结构——双向链表dlist

数据结构——双向链表dlist

前言&#xff1a;大家好&#x1f60d;&#xff0c;本文主要介绍了数据结构——双向链表dlist 一 双向链表定义 1. 双向链表的节点结构 二 双向链表操作 2.1 定义 2.2 初始化 2.3 插入 2.3.1 头插 2.3.2 尾插 2.3.3 按位置插 2.4 删除 2.4.1 头删 2.4.2 尾删 2.4.3 按…
阅读更多...
【PyTorch】.pt文件

【PyTorch】.pt文件

.pt文件是 PyTorch 中用于保存张量&#xff08;torch.Tensor&#xff09;或模型&#xff08;torch.nn.Module&#xff09;的二进制文件格式。它使用 PyTorch 的序列化机制来保存数据&#xff0c;能够高效地存储和加载张量或模型的状态。 .pt 文件中存储的内容 1. 张量&#x…
阅读更多...
最新文章

Copyright @ 2022~2023