当前位置: 首页 > article >正文

【算法】动态规划

头像
⭐️个人主页:@小羊
⭐️所属专栏:Linux
很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~

动图描述

目录

  • 动态规划总结
    • 1、常见动态规划
      • Fibonacci数列
      • 杨辉三角
      • 最小花费爬楼梯
      • 孩子们的游戏
    • 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;
    }
};

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


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

头像

http://www.kler.cn/a/588399.html

相关文章:

  • 3个 Vue nextTick 原理的关键点
  • (七)Spring Boot学习——Redis使用
  • Windows 注册表、定时任务与开机自启
  • 基于有限状态机的数字电路设计:Verilog 实践与探索
  • 柯南ED35 Hello Mr. My Yesterday日文歌词附假名注音,祭奠逝去的青春
  • 如何向 Linux 中加入一个 IO 扩展芯片
  • 4060ti-16G显卡部署deepseek-32B(支持联网搜索)
  • Android Room 框架表现层源码深度剖析(三)
  • Spring MVC 核心组件详解
  • Go语言进化之旅:从1.18到1.24的语法变革
  • 【SpringMVC】常用注解:@MatrixVariable
  • Spark sql 中row的用法
  • 深度学习 Deep Learning 第3章 概率论与信息论
  • 【C++初阶】模板初阶
  • C++内存管理(复习)
  • 游戏成瘾与学习动力激发策略研究——了解“情感解离”“创伤理论”
  • OpenHarmony项目的应用在DevEco Studio配置项目中固定的一键签名
  • android ConstraintLayout布局 实战:打造复杂界面的最佳实践
  • 网络规划设计师软考个人学习资料分享
  • stl之string的详解