算法刷题-动态规划-1

算法刷题-动态规划-1

  • 不同路径
  • 不同路径||
    • 方法一:
    • 方法二
  • 第N个泰波那契数
    • 递归写法
    • 滚动数组
  • 三步问题
    • 递归操作
    • 滚动数组
  • 使用最小画法爬楼梯
    • 递归
  • 解码方法
    • 方法一
    • 方法二:(大佬讲解)

不同路径

在这里插入图片描述
在这里插入图片描述

//机器人不同的路径进入到指定的地点
public static int uniquepath(int m, int n) {if (m <= 0 || n <= 0){return 0;}int[][] dp = new int[m][n];//初始化//如果只有i,j中有一个为0,那么机器人行走的方向只能有一种方式for (int i = 0; i < m; i++){dp[i][0] = 1;}for (itn i = 0; i < n; i++)  {dp[0][i] = 1;  }//推导出dp[m-1][n-1],因为定义dp[i][j]就是表示的是在[i][j]点  //不同的路径的数目  for (itn 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];    }

不同路径||

在这里插入图片描述

在这里插入图片描述
![在这里插入图片描述](https://img-blog.csdnimg.cn/55c59dbc1da64e20aed014ff76118002.png)

方法一:

大佬讲解
在这里插入图片描述

class Solution {
public:/*** 1. 确定dp数组下标含义 dp[i][j] 从(0,0)到(i,j)可能的路径种类;* 2. 递推公式 dp[i][j] = dp[i-1][j] + dp[i][j-1] 但是需要加限制条件就是没有障碍物的时候*    if(obstacleGrid[i][j] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];* 3. 初始化 当obstacleGrid[i][j] == 0时,dp[i][0]=1 dp[0][i]=1 初始化横竖就可;* 4. 遍历顺序 一行一行遍历;* 5. 推导结果;*/int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {/* 计算数组大小 */int m = obstacleGrid.size();int n = obstacleGrid[0].size();/* 定义dp数组 */vector<vector<int>> dp(m,vector<int>(n,0));/* 初始化dp数组 */for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++)dp[i][0] = 1; for(int i = 0; i < n && obstacleGrid[0][i] == 0; i++)   dp[0][i] = 1;      /* 一行一行遍历 */     for(int i = 1; i < m; i++) {     for(int j = 1; j < n; j++) {     /* 去除障碍物 */     if(obstacleGrid[i][j] == 1) continue;     dp[i][j] = dp[i-1][j] + dp[i][j-1];     }}return dp[m-1][n-1];     }
};

方法二

多加一行和一列的虚拟节点,防止出现越界的情况,
把它们初始化成0,但是要保证第一个节点初始化成1.
dp[0][1] = 1;


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

第N个泰波那契数

在这里插入图片描述


递归写法

1。先确定函数的一定是什么dp[ i ] 表示:第 i 个泰波那契数
2。题目中的关系代数是 dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ] + dp[ i - 3。边界是T(0)=0,T(1)=1,T(2)=1T(0)=0, T(1)=1,
4。初始化为dp[ 0 ] = 0,dp[ 1 ] = 1,dp[ 2 ] = 1

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

滚动数组

class Solution {
public:int tribonacci(int n) {if (n == 0) {return 0;}if (n <= 2) {  return 1;  }int p = 0, q = 0, r = 1, s = 1;  for (int i = 3; i <= n; ++i) {  p = q;  q = r;  r = s;  s = p + q + r;  }return s;  }
};

三步问题

在这里插入图片描述

这就是老油条的步骤了,
先确定自己定义的函数,然后找出关系式,然后确定初始值

递归操作

class Solution {  
public:  int waysToStep(int n) {  vector<in#t> dp(n + 1);  const int MOD = 1e9 + 7;  //边界问题    if (n == 1 || n == 2) return n;    if (n == 3) return 4;    //初始化定义    dp[1] = 1, dp[2] = 2, dp[3] = 4;    for (int i = 4; i <= n; i++) {   dp[i] = ((dp[i - 3] + dp[i - 2]) % MOD + dp[i - 1]) % MOD;   }return dp[n];   }
};

滚动数组

class Solution {    
public:    int waysToStep(int n) {     int a=1,b=2,c=4,i;     for(i=2;i<=n;i++){     long long t=(a+b)%1000000007;     t=(t+c)%1000000007;     a=b;     b=c;     c=t;     }return a;     }
};

使用最小画法爬楼梯

在这里插入图片描述
在这里插入图片描述

题目要求的是到达第n级台阶楼层顶部的最小花费,可以用动态规划来解,下面一步一步来讲怎样确定状态空间、怎样给出状态转移方程。

递归

  1. 大佬讲解

  2. 最近的一步有两种情况,

  3. 从 dp[ i - 1 ] 走一步过来,支付cost[ i - 1 ] 的费用; 1. 从 dp[ i - 1 ] 走一步过来,支付cost[ i - 1 ] 的费用;

  4. 从 dp[ i - 2 ] 走两步过来,支付cost[ i - 2 ] 的费用。
    而 dp[ i ] 就是到达 i 位置的最小花费,
    那我们就能得出状态转移方程:
    dp [ i ] = min( dp[ i - 1 ] + cost[ i - 1 ],dp[ i - 2 ] + cost[ i - 2 ] )


class Solution {  
public:  int minCostClimbingStairs(vector<int>& cost) {  int n = cost.size();  // 创建dp表,这样初始化默认填充的是 0   vector<int> dp(n + 1);  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];  }
};

解码方法

在这里插入图片描述

在这里插入图片描述

方法一

动态规划的使用:
1。确立dp 数组的定义,代表的是 dp[i] 位置代表的是第i个位置时候解码方法的总数。
2。找关系代数=

  1. s[ i ] 单独解码,如果是单独解码,当 s[ i ] 的值是 1~9 的时候可以自己解码,
    自己解码的方案数就是 dp[ i - 1 ],如果 s[ i ] 的值是 0,那方案数就是0,整体解码失败,

  2. s[ i ] 和 s[ i - 1 ] 一起解码,当 s[ i - 1 ] * 10 + s[ i ] 的值是 10~26 的时候就可以解码,
    而解码数就是 dp[ i - 2 ],如果解码失败,不在这个区间内,那方案数就也是0。
    3。初始化dp数组,
    初始化 dp[ 0 ] 和 dp[ 1 ] 位置,
    dp[ 0 ] 位置,如果s[ 0 ] 解码成功就是1,不成功就是0
    dp[ 1 ] 位置,如果 dp[ 1 ] 能自己解码,就 + 1,如果能跟 dp[ 0 ] 一起解码,就再 + 1,
    如果dp[ 1 ] 两种情况都不能解码,就是0。(所以可能是0, 1, 2)

class Solution {
public:int numDecodings(string s) {int n = s.size();vector<int> dp(size);dp[0] = s[0] != '0';if (size == 1) return dp[0];if (s[0] != '0' && s[1] != '0') dp[1]++;int t = (s[0] - '0') * 10 + (s[1] - '0');if (t >= 10 && t <= 26) dp[1]++;for (int i = 2; i < size; i++) {if (s[i] != '0') dp[i] += dp[i - 1]; t = (s[i - 1] - '0') * 10 + (s[i] - '0');if (t >= 10 && t <= 26) dp[i] += dp[i - 2]; //一起解码}return dp[n - 1];}
};

方法二:(大佬讲解)

在这里插入图片描述

class Solution {
public:int numDecodings(string s) {if (s[0] == '0') return 0;int n = s.size();vector<int> dp(n + 1, 1);//dp[0]表示s[-1]的状态, dp[1] 表示 s[0]的状态//dp[i] 表示 s[i-1]的状态for (int i = 2; i <= n; i++) {if (s[i - 1] == '0') {if (s[i - 2] == '1' || s[i - 2] == '2')//唯一译码,不增加情况dp[i] = dp[i - 2]; else//这里要好好理解一下,比如给定340, 输出可行的编码数为0, 因为0和40都无法转换  return 0;  }else if (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] >= '1' && s[i - 1] <= '6')dp[i] = dp[i - 1] + dp[i - 2];  else//当上述条件都不满足,维持上一个状态  dp[i] = dp[i - 1];  }//for(auto c:dp) cout << c << ",";  return dp[n];//返回dp[n] 即最后 s[n-1] 的状态  }
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SpringBoot : ch06 整合 web (一)

前言 SpringBoot作为一款优秀的框架&#xff0c;不仅提供了快速开发的能力&#xff0c;同时也提供了丰富的文档和示例&#xff0c;让开发者更加容易上手。在本博客中&#xff0c;我们将介绍如何使用SpringBoot来整合Web应用程序的相关技术&#xff0c;并通过实例代码来演示如何…

“图纸保密大作战:上海迅软DSE解决方案守护机械公司核心资料

机械行业是我国重要的工业制造行业之一&#xff0c;相关企业在发展中往往需要用到ERP、PDM、PLM等系统来对产品信息进行管理&#xff0c;其中便涉及到大量文档和图纸等重要数据。然而随着业务的快速发展和数字化转型&#xff0c;机械行业也面临着如数据泄露、外来袭击攻击、内部…

华为obs上传下载-Java版 2023-11-23

弄了半天&#xff0c;老师帮弄成功了&#xff0c;经过同意&#xff0c;分享到网上&#xff0c;希望能帮助更多人&#xff0c;至于怎么弄的&#xff0c;我也不知道。 创建idea项目后&#xff0c;项目结构&#xff0c;对应文件没有的创一个 pom.xm 注意改Java版本&#xff0c;我…

AIGC前沿技术与数字创新应用合作交流和论坛发布活动圆满落幕

2023年11月17日下午&#xff0c;AIGC前沿技术与数字创新应用合作交流和论坛发布活动在北京市海淀区牡丹科技楼B座B1报告厅成功举办。 在这个以技术为驱动力的时代&#xff0c;AIGC等这些前沿技术正以惊人的速度改变着我们的生活和产业格局。利用新兴技术和数字化工具来解决问题…

vite vue3配置eslint和prettier以及sass

准备 教程 安装eslint 官网 vue-eslint ts-eslint 安装eslint yarn add eslint -D生成配置文件 npx eslint --init安装其他插件 yarn add -D eslint-plugin-import eslint-plugin-vue eslint-plugin-node eslint-plugin-prettier eslint-config-prettier eslint-plugin…

【性能测试】稳定性/并发压力测试的TPS计算+5W并发场景设计...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、稳定性测试TPS…

【MySQL】索引与事务

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文录入于《MySQL》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&a…

局域网内Ubuntu上搭建Git服务器

1.在局域网内选定一台Ubuntu电脑作为Git服务端&#xff1a; (1).新建用户如为fbc&#xff0c;执行如下命令&#xff1a;需设置密码&#xff0c;此为fbc sudo adduser fbc (2).切换到fbc用户&#xff1a;需密码&#xff0c;此前设置为fbc su fbc (3).建一个空目录作为仓…

buildadmin+tp8表格操作(1)----表头上方添加按钮和自定义按钮

buildAdmin 的表头上添加一些按钮&#xff0c;并实现功能 添加按钮 <template><!-- buttons 属性定义了 TableHeader 本身支持的顶部按钮&#xff0c;仅需传递按钮名即可 --><!-- 这里的框架自带的 顶部按钮 分别有 刷新 &#xff0c; 添加&#xff0c; 编辑&…

HCIP-一、RSTP 特性及安全

一、RSTP 特性及安全 实验拓扑实验需求及解法 实验拓扑 实验需求及解法 //1.SW1/2/3是企业内部交换机&#xff0c;如图所示配置各设备名称。 //2.配置VLAN&#xff0c;需求如下&#xff1a; //1&#xff09;SW1/2/3创建vlan10 [SW1]vlan batch 10 [SW2]vlan batch 10 [SW3]vla…

1.8w 字详解 SQL 优化

来源&#xff1a;捡田螺的小男孩 1、MySQL的基本架构 2、SQL优化 3、explain执行计划常用关键字详解 很多朋友在做数据分析时&#xff0c;分析两分钟&#xff0c;跑数两小时&#xff1f; 在使用SQL过程中不仅要关注数据结果&#xff0c;同样要注意SQL语句的执行效率。 本文…

层层剥开Android14升级后异常弹框的神秘面纱

本篇文章将会通过研究源码的方式给您讲述Android系统升级到Android14后出现的两个异常弹框并给出消除它们的方案。闲话少叙&#xff0c;我们开始。 问题描述 在Android 14升级后&#xff0c;出现两个弹窗的异常情况。这里是异常的截图&#xff1a; 接下来&#xff0c;我们对这…

运行代码时不同软件的参数写法

目录 pycharm终端 pycharm 如下图所示&#xff0c;不同参数间不需要什么间隔什么东西 终端 如下图所示&#xff0c;不同参数间需要用一个符号来间隔

Java8新特性 ----- Lambda表达式和方法引用/构造器引用详解

前言 在讲一下内容之前,我们需要引入函数式接口的概念 什么是函数式接口呢? 函数式接口&#xff1a;有且仅有一个抽象方法的接口 java中函数式编程的体现就是Lambda表达式,你可以认为函数式接口就是适用于Lambda表达式的接口. 也可以加上注解来在编译层次上限制函数式接口 Fun…

渲染器——双端Diff算法

简单 Diff 算法利用虚拟节点的 key 属性&#xff0c;尽可能地复用 DOM 元素&#xff0c;并通过移动 DOM 的方式来完成更新&#xff0c;从而减少不断地创建和销毁DOM 元素带来的性能开销。但是&#xff0c;简单 Diff 算法仍然存在很多缺陷&#xff0c;这些缺陷可以通过双端 Diff…

Nginx部署前端项目

Nginx部署前端项目 1.在nginx官网http://nginx.org/en/download.html &#xff0c;下载稳定版本&#xff1a; 2.解压后&#xff0c;点击根目录中的nginx.exe即可启动Nginx&#xff0c;或是在nginx安装目录中启动cmd并输入以下命令启动&#xff1a; nginx.exe 或 start nginx3…

Cannot read properties of undefined (reading ‘resetFields‘)“ 报错解决

遇到这种报错 先去相关页面搜索关键字 定位到具体的报错代码 Cannot read properties of undefined (reading ‘resetFields’)" 关键字&#xff1a;resetFields 此方法作用&#xff1a;对整个表单进行重置 将所有字段值重置为初始值并移除校验结果 报错场景&#xff1a;…

SWT/Jface(1): 表格的创建和渲染

前言 使用JFace创建表格还是比较方便的, 如果仅仅是创建空表格的话, 以下2步即可完成: 创建TableViewer对象, 指定样式, 比如是否支持多行选择, 有无边框, 是否支持滚动条等创建TableColumn对象: 包括列展示名称, 宽度和样式等, 最终绑定到table对象 实例 创建表格 //注意…

深入浅出 Linux 中的 ARM IOMMU SMMU I

Linux 系统下的 SMMU 介绍 在计算机系统架构中&#xff0c;与传统的用于 CPU 访问内存的管理的 MMU 类似&#xff0c;IOMMU (Input Output Memory Management Unit) 将来自系统 I/O 设备的 DMA 请求传递到系统互连之前&#xff0c;它会先转换请求的地址&#xff0c;并对系统 I…

灵活运用Vue 3中的setup函数—深入解析Composition API

新建项目&#xff0c;项目主入口为App.vue&#xff08;主组件&#xff09;&#xff0c;新建child.vue&#xff08;子组件&#xff09;。 1.1 setup 执行 时机问题 1.在主组件里引入子组件和ref&#xff1a; import {ref} from vue import child from ./components/child.vue2…