动态规划-

关键词:

           重叠子问题;每一个状态一定是由上一个状态推导出来(类似数列a^n = f(a^n-1,a^n-2))

步骤:        

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

题目: 

509. 斐波那契数 

动规五部曲:

这里我们要用一个一维dp数组来保存递归的结果

  1. 确定dp数组以及下标的含义

dp[i]的定义为:第i个数的斐波那契数值是dp[i]

  1. 确定递推公式

为什么这是一道非常简单的入门题目呢?

因为题目已经把递推公式直接给我们了:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

  1. dp数组如何初始化

题目中把如何初始化也直接给我们了,如下:

dp[0] = 0;
dp[1] = 1;
  1. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

  1. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2],我们来推导一下,当N为10的时候,dp数组应该是如下的数列:

0 1 1 2 3 5 8 13 21 34 55

class Solution {
public:int fib(int N) {if (N <= 1) return N;vector<int> dp(N + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= N; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[N];}
};

 70. 爬楼梯

 

  1. 确定dp数组以及下标的含义

dp[i]: 爬到第i层楼梯,有dp[i]种方法

  1. 确定递推公式

从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来。

首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么。

还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!

所以dp[i] = dp[i - 1] + dp[i - 2] 。

  1. dp数组如何初始化

dp[1] = 1,dp[2] = 2,这个初始化大家应该都没有争议的。

所以我的原则是:不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义。

  1. 确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的

  1. 举例推导dp数组

举例当n为5的时候,dp table(dp数组)应该是这样的

// 版本一
class Solution {
public:int climbStairs(int n) {if (n <= 1) return n; // 因为下面直接对dp[2]操作了,防止空指针vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) { // 注意i是从3开始的dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

746. 使用最小花费爬楼梯

 

  1. 确定dp数组以及下标的含义

使用动态规划,就要有一个数组来记录状态,本题只需要一个一维数组dp[i]就可以了。

dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]

  1. 确定递推公式

可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]

dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢?

一定是选最小的,所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

  1. dp数组如何初始化

所以初始化 dp[0] = 0,dp[1] = 0;

  1. 确定遍历顺序

因为是模拟台阶,而且dp[i]由dp[i-1]dp[i-2]推出,所以是从前到后遍历cost数组就可以了。

  1. 举例推导dp数组

拿示例2:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ,来模拟一下dp数组的状态变化,如下:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0; // 默认第一步都是不花费体力的dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {//与上一题区别在于这里取两者最小dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};

 62. 不同路径

 

按照动规五部曲来分析:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。

  1. 确定递推公式

想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。

 dp[i - 1][j] 是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。

所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来。

  1. dp数组的初始化

如何初始化呢,首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条,那么dp[0][j]也同理。

所以初始化代码为:

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
  1. 确定遍历顺序

这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。

这样就可以保证推导dp[i][j]的时候,dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

  1. 举例推导dp数组

如图所示:

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 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 - 1][n - 1];}
};

 

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

【数据结构】顺序表实现的层层分析!!

关注小庄 顿顿解馋◍˃ ᗜ ˂◍ 引言&#xff1a;本篇博客我们来认识数据结构其中之一的顺序表&#xff0c;我们将认识到什么是顺序表以及顺序表的实现&#xff0c;请放心食用~ 文章目录 一.什么是顺序表&#x1f3e0; 线性表&#x1f3e0; 顺序表 二.顺序表的实现&#x1f3e0…

【教3妹学编程-算法题】匹配模式数组的子数组数目 I

3妹&#xff1a;2哥2哥&#xff0c;你有没有看到上海女老师出轨男学生的瓜啊。 2哥 : 看到 了&#xff0c;真的是太毁三观了&#xff01; 3妹&#xff1a;是啊&#xff0c; 老师本是教书育人的职业&#xff0c;明确规定不能和学生谈恋爱啊&#xff0c;更何况是出轨。 2哥 : 是啊…

导出本地环境venv包whl文件。

把python环境 venv 对应包的文件导出成whl文件 将 Python 虚拟环境中包导出到文件&#xff0c;可以方便地在其他电脑上安装相同的环境&#xff0c;无需重复下载。 使用 pip freeze 和 pip download 使用 pip freeze 命令列出所有已安装的包和版本号保存到 requirements.txt …

Sora----打破虚实之间的最后一根枷锁----这扇门的背后是人类文明的晟阳还是最后的余晖

目录 一.Sora出道即巅峰 二.为何说Sora是该领域的巨头 三.Sora无敌的背后究竟有怎样先进的处理技术 1.Spacetime Latent Patches 潜变量时空碎片&#xff0c;建构视觉语言系统 2.扩散模型与Diffusion Transformer&#xff0c;组合成强大的信息提取器 3.DiT应用于潜变量时…

小区视频汇聚与智能监管方案:老破小升级改造与小区智慧化建设

一、需求背景 在当今数字化时代&#xff0c;智慧小区已成为城市建设的必然趋势。加快小区智能化改造&#xff0c;不断完善小区管理和服务&#xff0c;彻底改变粗放型管理方式已经成为当前小区智慧化趋势的重要任务。其中&#xff0c;智能视频监控系统在提高小区安全性和管理效…

T-Dongle-S3开发笔记——分区表

参考&#xff1a; ESP32之 ESP-IDF 教学&#xff08;十三&#xff09;—— 分区表_esp32分区表-CSDN博客 分区表 - ESP32 - — ESP-IDF 编程指南 latest 文档 (espressif.com) 分区表是 ESP32 划分内部 flash 闪存的清单&#xff0c;它将 flash 划分为多个不同功能的区域用于…

交通强国,数字引领|易知微数字孪生智慧港口,探索未来港口的无限可能

点击下载了解易知微数字孪生智慧港口解决方案&#x1f449;https://easyv.cloud/solution/port/?tcsdn 2023年12月&#xff0c;为推动智慧港口和智慧航道建设发展&#xff0c;加快建设交通强国水运&#xff0c;交通运输部发布《关于加快智慧港口和智慧航道建设的意见》。到20…

哪种游泳耳机品牌更好?2024四款甄选高评分榜单好物!

在繁忙的都市生活中&#xff0c;游泳已经成为了许多人释放压力、保持健康的重要方式。而随着科技的进步&#xff0c;游泳耳机也逐渐走进了人们的视野&#xff0c;让音乐与游泳完美结合&#xff0c;为游泳爱好者带来了全新的运动体验。然而&#xff0c;在琳琅满目的游泳耳机市场…

vite为什么编译比webpack快

启动速度&#xff1a;Vite在启动时不需要打包&#xff0c;因为它支持ES模块加载&#xff0c;不需要编译和打包所有模块的依赖。这意味着Vite在启动时不需要像Webpack那样构建整个项目的文件&#xff0c;因此启动速度更快。 1 vite 采用 es 新规范 vite 中的 main.ts 中可以直…

camunda源代码编译运行(三):验证camunda API接口功能

接上一篇文章&#xff1a;camunda源代码编译运行&#xff08;二&#xff09;&#xff1a;构建并运行camunda源代码工程 4.1、发布流程模型 先通过camunda的流程设计器设计一个流程&#xff0c;命名为&#xff1a;UserTask Flow1&#xff0c;然后发布流程&#xff0c;发布流程…

C语言第二十九弹---浮点数在内存中的存储

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 目录 1、浮点数在内存中的存储 1.1、练习 1.2、浮点数怎么转化为二进制 1.3、浮点数的存储 1.3.1、浮点数存的过程 1.3.2、浮点数取的过程 1.3、题目解析…

jquery 简介与解析

jQuery是一个快速、小巧且功能丰富的JavaScript库。它简化了诸如HTML文档遍历和操作、事件处理、动画以及Ajax操作等任务。jQuery的设计理念是“写得更少&#xff0c;做得更多”&#xff0c;这意味着通过jQuery&#xff0c;可以用更少的代码完成更多的工作。 主要特点&#xff…

Druid无法登录监控页面

问题表现&#xff1a;在配置和依赖都正确的情况下&#xff0c;无法通过配置的用户名密码登录Druid的监控页面 检查配置发现 配置的用户名和密码和请求中参数是一致的&#x1f914; Debug发现 ResourceServlet 是Druid的登录实现&#xff0c; 且调试发现usernameParam是null&am…

java集合解析-Collection 类型

Java 集合概览 Java 集合&#xff0c; 也叫作容器&#xff0c;主要是由两大接口派生而来&#xff1a; 一个是 Collection接口&#xff0c;主要用于存放单一元素&#xff1b; 另一个是 Map 接口&#xff0c;主要用于存放键值对。对于Collection 接口&#xff0c;下面又有三个…

骨传导什么牌子好?六大专业选购的黄金规则与避坑指导

谈论到运动时佩戴的耳机&#xff0c;骨传导耳机必须是话题中的热点。与传统耳机或入耳式耳机不同&#xff0c;骨传导耳机解放了你的耳道&#xff0c;让你在挥洒汗水的同时&#xff0c;也能享受音乐的魅力。更重要的是&#xff0c;它不会阻碍你听到周围的声音&#xff0c;这对于…

盘点自动化汽车生产线设备 数据采集分析联合各设备

1.机器人自动装配线 机器人自动装配线已成为汽车制造业中的常见场景。这些机器人在汽车组装的各个环节发挥关键作用&#xff0c;从焊接和铆接到零部件组装。它们不仅提高了装配速度&#xff0c;还确保了产品的一致性&#xff0c;降低了废品率。 2.3D打印技术 3D打印技术正在汽车…

医院信息系统(HIS):一文扫盲,算是所有信息系统里面复杂的

大家好&#xff0c;我是贝格前端工场&#xff0c;本期继续分享常见的B端管理系统&#xff0c;欢迎大家关注&#xff0c;如有B端写系统界面的设计和前端需求&#xff0c;可以联络我们。 一、什么是HIS系统 HIS系统&#xff08;Hospital Information System&#xff09;是医院信…

【操作系统】磁盘存储空间的管理

实验5 磁盘存储空间的管理 一、实验目的 磁盘是用户存放程序和数据的存储设备&#xff0c;磁盘管理的主要目的是充分有效地利用磁盘空间。本实验模拟实现磁盘空间的分配与回收&#xff0c;使学生对磁盘空间的管理有一个较深入的理解。 二、实验内容 实验任务&#xff1a;用位…

Canal + Kafka 同步 MySQL 数据到 Redis

解决缓存和数据库一致性问题 一般来说&#xff0c;缓存中的数据没什么问题&#xff0c;但是数据库更新后&#xff0c;就容易出现缓存&#xff08;Redis&#xff09;和数据库&#xff08;MySQL&#xff09;间的数据一致性问题。由于写和读是并发的&#xff0c;没法保证顺序&…