数据结构与算法再探（六）动态规划

目录

动态规划 (Dynamic Programming, DP)

动态规划的基本思想

动态规划的核心概念

动态规划的实现步骤

动态规划实例

1、爬楼梯

c++ 递归（超时）需要使用记忆化递归

循环

2、打家劫舍

3、最小路径和

4、完全平方数

5、最长公共子序列

6、0-1背包问题

总结

动态规划 (Dynamic Programming, DP)

释义：动态规划是一种解决复杂问题的优化方法，通过将大问题拆解成小问题，逐步解决小问题，最终得到大问题的解。它通常用于求解具有最优子结构和重构子问题的优化问题。C++中的动态规划算法应用广泛，尤其是在最短路径、背包问题、最长公共子序列、矩阵链乘法等领域。

动态规划的基本思想

动态规划方法通过建立状态转移方程（recurrence relation）来表示问题的子问题之间的关系。每个子问题的解只计算一次，然后保存起来避免重复计算，从而达到减少计算量的目的。常见的动态规划问题通常可以通过两种方式实现：自顶向下的递归（带记忆化）和自底向上的迭代。

动态规划的核心概念

最优子结构问题的最优解可以通过子问题的最优解得到。换句话说问题的最优解包含了子问题的最优解
重叠子问题

问题可以被分解成多个子问题，且这些子问题在计算过程中会被多次求解。

状态转移方程动态规划的核心是通过状态转移方程将大问题分解为小问题，进而通过小问题的解推导出大问题的解

动态规划的实现步骤

定义状态首先定义子问题的状态。通常状态的定义取决于问题的具体性质。例如，在最短路径问题中，可以定义状态为当前节点到起点的最短路径长度
初始化状态为状态的初值赋值。通常，某些边界条件会初始化为已知值。
状态转移方程根据问题的性质，推导出状态转移方程，描述如何从当前状态推导到下一个状态
计算最优解根据状态转移方程，从最简单的子问题开始逐步计算，直到得到最终问题的解
结果回溯（如果需要）：如果问题要求返回具体的解路径（例如路径、序列等），则需要在求解过程中保存路径信息，最后回溯得到结果

动态规划实例

1、爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

状态定义：dp[i]表示爬到第 i 阶楼梯的不同方法数。

状态转移方程：dp[i] =dp[i-1]+dp[i-2]，即爬到第 i 阶楼梯可以从第 i-1 阶或第 i-2 阶跳跃过来。

为什么 d[i] = d[i-1] + d[i-2] 不会重复包含 d[i-2]？
在动态规划中，d[i] 表示到达第 i 阶楼梯的总方法数。当计算 d[i] 时，d[i-1] 和 d[i-2] 分别表示到达第 i-1 阶和第 i-2 阶楼梯的方法数。这两个数并没有交叉或重复计算的部分，它们分别独立表示从不同阶梯出发的跳跃方式。更具体的解释：d[i-1] 代表的是从第 i-1 阶楼梯跳一步到达第 i 阶楼梯的方法数。d[i-2] 代表的是从第 i-2 阶楼梯跳两步到达第 i 阶楼梯的方法数。
这两个值分别代表不同的跳跃方式：从 i-1 到 i 是一次跳跃，跳跃的过程中，不需要考虑 i-2。
从 i-2 到 i 是两次跳跃，这一步也不会再次涉及到 i-1。
因此，d[i-1] 和 d[i-2] 并没有重叠，它们分别计算的是不同的路径，最终的 d[i] = d[i-1] + d[i-2] 是将这两条路径相加，得到的总方法数。

c++ 递归（超时）需要使用记忆化递归

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2) return n;
        return climbStairs(n-1)+climbStairs(n-2);
    }
};

//记录搜素值
vector<int> res;
int dfs(int i){
    if(i<=1){
        return 1;
    }
    if(res[i]){
        return res[i];
    }
    return res[i]=dfs(i-1)+dfs(i-2);
}

循环

    int climbStairs(int n) {
         if (n <= 2)
             return n;
         vector<int> dp(n + 1, 1);
         for (int i = 2; i <= n; ++i) {
             dp[i] = dp[i - 1] + dp[i - 2];
         }
         return dp[n];
     }
  //空间优化
    int climbStairs(int n) {
        if (n <= 2)
            return n;
        int pre2 = 1, pre1 = 2, cur;
        for (int i = 2; i < n; ++i) {
            cur = pre1 + pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return cur;
    }

2、打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

设 dp[i] 表示偷窃前 i 家房子时的最大金额。显然，对于每个房子，存在两个选择：偷窃第 i 家房子：如果你偷窃第 i 家房子，那么你不能偷窃第 i-1 家房子，因此最大金额是 dp[i-2] + nums[i]，其中 nums[i] 表示第 i 家房子的金额。
不偷窃第 i 家房子：那么最大金额就是 dp[i-1]，即偷窃前 i-1 家房子时的最大金额。因此，递推关系式为：dp[i]=max(dp[i−1],dp[i−2]+nums[i])其中，dp[0] 为偷窃第一家房子的金额，dp[1] 为偷窃前两家房子时的最大金额。

状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始状态：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。

  int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n,0);
        if(n==1){return nums[0];}
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<n;++i){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
//空间优化
    int rob(vector<int>& nums) {
        int n=nums.size();
        //vector<int> dp(n,0);
        if(n==1){return nums[0];}
        auto pre=0;
        auto cur=0;
        int res=0;
        for(int i=0;i<n;++i){
            res=max(cur,pre+nums[i]);
            pre=cur;
            cur=res;
        }
        return res;
    }

3、最小路径和

64. 最小路径和 - 力扣（LeetCode）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

状态定义：用 dp[i][j] 表示到达位置 (i, j) 的最小路径和。
状态转移：从上方到达 (i, j) 的路径和为 dp[i-1][j] + grid[i][j]。从左方到达 (i, j) 的路径和为 dp[i][j-1] + grid[i][j]。因此，状态转移方程为：dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]；其中，dp[i-1][j] 和 dp[i][j-1] 分别表示到达上方和左方的最小路径和。

初始状态：dp[0][0] = grid[0][0]，即起点的值。第一行和第一列的值需要单独处理，因为它们只能从一个方向到达：第一行：dp[0][j] = dp[0][j-1] + grid[0][j]；第一列：dp[i][0] = dp[i-1][0] + grid[i][0]
返回结果：最终的结果为 dp[m-1][n-1]，即到达右下角的最小路径和。

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

4、完全平方数

279. 完全平方数 - 力扣（LeetCode）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

状态定义：用 dp[i] 表示和为 i 的最小完全平方数的数量。
状态转移：对于每个 i，我们可以尝试用每个小于等于 i 的完全平方数 j*j 来更新 dp[i]：dp[i]=min(dp[i],dp[i−j∗j]+1), 其中 j 是从 1 到 \sqrt{i} 的整数(位置 i 只依赖 i - j*j 的位置，如 i - 1、 i - 4、 i - 9 等等，才能满足完全平方分割的条件)。
初始状态：dp[0] = 0，表示和为 0 时不需要任何数。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i<=n;++i){
            for(int j=1;j*j<=i;++j){
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};

5、最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

状态定义：用 dp[i][j] 表示 text1 的前 i 个字符与 text2 的前 j 个字符的最长公共子序列的长度。
状态转移：如果 text1[i-1] == text2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符相等时，公共子序列长度加一。如果 text1[i-1] != text2[j-1]，那么 dp[i][j] = \max(dp[i-1][j], dp[i][j-1])，表示当前字符不相等时，最长公共子序列的长度为去掉当前字符后的最大值。
初始状态：dp[0][j] = 0 和 dp[i][0] = 0，表示任意一个字符串为空时，公共子序列长度为 0。
返回结果：最终的结果为 dp[m][n]，其中 m 和 n 分别是 text1 和 text2 的长度。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

6、0-1背包问题

有 n 个物品，每个物品 i 有一个重量 weights[i] 和一个价值 values[i]。背包的最大容量为 W。需要找到一个选择方案，使得所选物品的总重量不超过 W，并且总价值最大。动态规划的思路
状态定义：用 dp[i][j] 表示前 i 个物品中，能够放入容量为 j 的背包的最大价值。
状态转移：如果不选择第 i 个物品，最大价值为 dp[i-1][j]。如果选择第 i 个物品，最大价值为 values[i-1] + dp[i-1][j-weights[i-1]]（前提是 j 大于等于 weights[i-1]）。
因此，状态转移方程为：dp[i][j]=max(dp[i−1][j],values[i−1]+dp[i−1][j−weights[i−1]])if j≥weights[i−1]初始状态：dp[0][j] = 0，表示没有物品时，最大价值为 0。返回结果：最终的结果为 dp[n][W]，即使用所有物品时，背包容量为 W 的最大价值。

int knapsack(vector<int> weights, vector<int> values, int N, int W)
{
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; ++i)
    {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 1; j <= W; ++j)
        {
            if (j >= w)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[N][W];
}

总结

动态规划是一种强大的方法，可以解决很多最优化问题。其核心思想是将问题拆解为子问题，通过记忆化或迭代的方式避免重复计算，从而提高效率。在C++中，动态规划的实现通常涉及状态定义、状态转移方程的推导以及最终解的计算。通过具体的算法问题（如背包问题、最长公共子序列、爬楼梯问题等）来理解和应用动态规划，可以帮助解决复杂的优化问题。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/958436.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

如何使用CRM数据分析优化销售和客户关系？

如何使用CRM数据分析优化销售和客户关系？

嘿&#xff0c;大家好&#xff01;你有没有想过为什么有些公司在市场上如鱼得水&#xff0c;而另一些却在苦苦挣扎&#xff1f;答案可能就藏在他们的销售策略和客户关系管理&#xff08;CRM&#xff09;系统里。今天我们要聊的就是如何通过有效的 CRM 数据分析来提升你的销售额…
阅读更多...
语音转文字的先驱-认识Buzz的前世今生

语音转文字的先驱-认识Buzz的前世今生

Buzz 是一款基于 OpenAI Whisper 模型开发的开源语音转文字工具&#xff0c;其历史可以追溯到 Whisper 模型的推出&#xff0c;并在之后逐渐发展为一个功能强大且广泛使用的工具。以下是关于 Buzz 的详细历史介绍&#xff1a; 1. Whisper 模型的背景 Buzz 的核心是 OpenAI 开…
阅读更多...
宝塔Linux+docker部署nginx出现403 Forbidden

宝塔Linux+docker部署nginx出现403 Forbidden

本文主要讲述了宝塔docker部署nginx出现403 Forbidden的原因&#xff0c;以及成功部署前端的方法步骤。 目录 1、问题描述2、问题检测2.1 检测监听端口是否异常2.2 检测Docker容器是否异常2.2.1 打开宝塔Linux的软件商店&#xff0c;找到Docker管理器&#xff0c;查看前端容器是…
阅读更多...
LabVIEW项目中的工控机与普通电脑选择

LabVIEW项目中的工控机与普通电脑选择

工控机&#xff08;Industrial PC&#xff09;与普通电脑在硬件设计、性能要求、稳定性、环境适应性等方面存在显著差异。了解这些区别对于在LabVIEW项目中选择合适的硬件至关重要。下面将详细分析这两种设备的主要差异&#xff0c;并为LabVIEW项目中的选择提供指导。 ​ 硬件设…
阅读更多...
QT6 + CMAKE编译OPENCV3.9

QT6 + CMAKE编译OPENCV3.9

参考文档 [1] https://blog.csdn.net/rjkf_css/article/details/135676077 前提条件 配置好相关运行环境&#xff1a;QT6、OPENCV3.9的sources文件 OPENCV下载网页&#xff1a;https://opencv.org/releases/ QT6下载教程&#xff1a;https://blog.csdn.net/caoshangpa/article…
阅读更多...
消息队列篇--基础篇（消息队列特点，应用场景、点对点和发布订阅工作模式，RabbmitMQ和Kafka代码示例等）

消息队列篇--基础篇（消息队列特点，应用场景、点对点和发布订阅工作模式，RabbmitMQ和Kafka代码示例等）

1、消息队列的介绍 消息&#xff08;Message&#xff09;是指在应用之间传送的数据&#xff0c;消息可以非常简单&#xff0c;比如只包含文本字符串&#xff0c;也可以更复杂&#xff0c;可能包含嵌入对象。 消息队列&#xff08;Message Queue&#xff0c;简称MQ&#xff09…
阅读更多...
状态模式——C++实现

状态模式——C++实现

目录 1. 状态模式简介 2. 代码示例 3. 单例状态对象 4. 状态模式与策略模式的辨析 1. 状态模式简介 状态模式是一种行为型模式。 状态模式的定义&#xff1a;状态模式允许对象在内部状态改变时改变它的行为&#xff0c;对象看起来好像修改了它的类。 通俗的说就是一个对象…
阅读更多...
GESP202309 三级【进制判断】题解（AC）

GESP202309 三级【进制判断】题解（AC）

》》》点我查看「视频」详解》》》 [GESP202309 三级] 进制判断 题目描述 N N N 进制数指的是逢 N N N 进一的计数制。例如&#xff0c;人们日常生活中大多使用十进制计数&#xff0c;而计算机底层则一般使用二进制。除此之外&#xff0c;八进制和十六进制在一些场合也是常用…
阅读更多...
汽车敏捷开发：项目经理如何精准跟进项目流程

汽车敏捷开发：项目经理如何精准跟进项目流程

在敏捷开发环境中&#xff0c;项目经理身兼协调者、推动者、决策者等关键角色。 作为协调者&#xff0c;需在团队及部门间搭建沟通桥梁&#xff0c;确保信息流畅。 作为推动者&#xff0c;面对迭代中的技术难题、资源短缺等阻碍&#xff0c;要主动寻找解决方案&#xff0c;为…
阅读更多...
数据从前端传到后端入库过程分析

数据从前端传到后端入库过程分析

数据从前端传到后端入库过程分析 概述 积累了一些项目经验&#xff0c;成长为一个老程序员了&#xff0c;自认为对各种业务和技术都能得心应手的应对了&#xff0c;殊不知很多时候我们借助了搜索引擎的能力&#xff0c;当然现在大家都是通过AI来武装自己。 今天要分析的话题是…
阅读更多...
Netty 实战

Netty 实战

Netty实践 1 Netty 版本选择2 Netty 模版代码2.1 Server2.2 Client 3 组件3.1 EventLoop、EventLoopGroup3.1.1 EventLoop3.1.2 EventLoopGroup 3.2 Channel3.2.1 ChannelFuture3.2.2 CloseFuture 3.3 ChannelHandler3.2.1 常用的 ChannelInboundHandlerAdapter3.2.1.1 LineBas…
阅读更多...
Triton:内存高效注意力机制的实现与解析

Triton:内存高效注意力机制的实现与解析

Triton:内存高效注意力机制的实现与解析 引言 在深度学习领域&#xff0c;特别是自然语言处理&#xff08;NLP&#xff09;任务中&#xff0c;注意力机制是模型理解序列数据的关键组成部分。然而&#xff0c;随着模型规模和输入长度的增长&#xff0c;传统的注意力机制面临着…
阅读更多...
微信小程序使用上拉加载onReachBottom。页面拖不动。一直无法触发上拉的事件。

微信小程序使用上拉加载onReachBottom。页面拖不动。一直无法触发上拉的事件。

1&#xff0c;可能是原因是你使用了scroll-view的标签&#xff0c;用onReachBottom触发加载事件。这两个是有冲突的。没办法一起使用。如果页面的样式是滚动的是无法去触发页面的onReachBottom的函数的。因此&#xff0c;你使用overflow:auto.来使用页面的某些元素滚动&#xf…
阅读更多...
机器学习2 （笔记）（朴素贝叶斯，集成学习，KNN和matlab运用）

机器学习2 （笔记）（朴素贝叶斯，集成学习，KNN和matlab运用）

朴素贝叶斯模型 贝叶斯定理&#xff1a; 常见类型 算法流程 优缺点 集成学习算法 基本原理 常见方法 KNN&#xff08;聚类模型&#xff09; 算法性质&#xff1a; 核心原理&#xff1a; 算法流程 优缺点 matlab中的运用 朴素贝叶斯模型 朴素贝叶斯模型是基于贝叶斯…
阅读更多...
【2024年华为OD机试】(B卷,100分)- 非严格递增连续数字序列 （JavaScriptJava PythonC/C++）

【2024年华为OD机试】(B卷,100分)- 非严格递增连续数字序列 （JavaScriptJava PythonC/C++）

一、问题描述 题目描述 给定一个仅包含大小写字母和数字的字符串&#xff0c;要求找出其中最长的非严格递增连续数字序列的长度。非严格递增连续数字序列指的是序列中的数字从左到右依次递增或保持不变&#xff0c;例如 12234 就是一个非严格递增连续数字序列。 输入描述 输…
阅读更多...
Android中Service在新进程中的启动流程2

Android中Service在新进程中的启动流程2

目录 1、Service在客户端的启动入口 2、Service启动在AMS的处理 3、Service在新进程中的启动 4、Service与AMS的关系再续 上一篇文章中我们了解了Service在新进程中启动的大致流程&#xff0c;同时认识了与客户端进程交互的接口IApplicationThread以及与AMS交互的接口IActi…
阅读更多...
Three城市引擎地图插件Geo-3d

Three城市引擎地图插件Geo-3d

一、简介 基于Three开发&#xff0c;为Three 3D场景提供GIS能力和城市底座渲染能力。支持Web墨卡托、WGS84、GCJ02等坐标系&#xff0c;支持坐标转换&#xff0c;支持影像、地形、geojson建筑、道路&#xff0c;植被等渲染。支持自定义主题。 二、效果 三、代码 //插件初始化…
阅读更多...
Ubuntu环境 nginx 源码 编译安装

Ubuntu环境 nginx 源码 编译安装

ubuntu 终端 使用 wget 下载源码 sudo wget http://nginx.org/download/nginx-1.24.0.tar.gz解压刚下载的源码压缩包 nginx-1.24.0.tar.gz sudo tar -zxvf nginx-1.24.0.tar.gz 解压完成 产生 nginx-1.24.0 目录 进入该目录 cd ./nginx-1.24.0 目录下有一个可执行文件 con…
阅读更多...
【深度学习】神经网络实战分类与回归任务

【深度学习】神经网络实战分类与回归任务

第一步 读取数据 ①导入torch import torch ②使用魔法命令&#xff0c;使它使得生成的图形直接嵌入到 Notebook 的单元格输出中&#xff0c;而不是弹出新的窗口来显示图形 %matplotlib inline③读取文件 from pathlib import Path import requestsDATA_PATHPath("dat…
阅读更多...
60，【1】BUUCF web [RCTF2015]EasySQL1

60，【1】BUUCF web [RCTF2015]EasySQL1

先查看源码 1&#xff0c;changepwd&#xff08;修改密码&#xff09; <?php // 开启会话&#xff0c;以便使用会话变量 session_start();// 设置页面的内容类型为 HTML 并使用 UTF-8 编码 header("Content-Type: text/html; charsetUTF-8");// 引入配置文件&…
阅读更多...
最新文章

Copyright @ 2022~2023