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

对经典动态规划问题【爬台阶】的一些思考

背景

今天在做Leetcode题目时,做到了一道经典的动态规划问题:爬楼梯,题目的大致意思很简单,有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。在考虑这个问题的时候本人产生了以下的思考。

自己的思考

上4阶台阶=上1阶台阶方法和上3阶台阶方法之和+上2阶台阶方法和上2阶台阶方法之和+上3阶台阶方法和上1阶台阶方法之和,这种思路对吗?

对思路的验证

这种思路实际上是在尝试将问题分解为多个独立的情况,但这里存在一个逻辑错误。

我的思路中的错误在于,将“上2阶台阶的方法数”重复计算了两次,一次是作为到达第3阶台阶后上1阶(此时有一种情况是先上2阶,再上1阶,到达第3阶,最后再上1阶),另一次是作为到达第2阶台阶后上2阶(先上2阶,后面2阶分两次1阶)。实际上,到达第4阶台阶的方法数应该只计算一次“上2阶台阶”的情况。

正确的思路

让我们分析一下正确的思路:

  1. 上1阶台阶的方法数:到达第4阶台阶,你可以先上1阶,然后剩下的是上3阶台阶的方法数,即 dp[3]

  2. 上2阶台阶的方法数:到达第4阶台阶,你可以先上2阶,然后剩下的是上2阶台阶的方法数,即 dp[2]

  3. 上3阶台阶的方法数:到达第4阶台阶,你可以先上3阶,然后剩下的是上1阶台阶的方法数,即 dp[1]

正确的状态转移方程应该是:

d p [ n ] = d p [ n − 1 ] + d p [ n − 2 ] + d p [ n − 3 ] dp[n] = dp[n-1] + dp[n-2] + dp[n-3] dp[n]=dp[n1]+dp[n2]+dp[n3];

这个方程表示到达第 ( n ) 阶台阶的方法数是到达第 ( n-1 ) 阶、( n-2 ) 阶和 ( n-3 ) 阶台阶的方法数之和。这里没有重复计算任何情况,每个情况都被独立考虑了一次。

总结

之前的思考过程尝试将问题分解为多个部分,这是一个很好的方法,但是在合并这些部分时,需要确保没有重复计算任何情况。正确的方法是使用动态规划,确保每一步都是基于前几步的结果,并且没有重复或遗漏。

http://www.lryc.cn/news/423270.html

相关文章:

  • 开发一个能打造虚拟带货直播间的工具!
  • 汽车补光照明实验太阳光模拟器光源
  • MediaPipe人体姿态、手指关键点检测
  • 树上dp之换根dp
  • 2024/8/13 英语每日一段
  • Java多线程练习(1)
  • AI高级肖像动画神器LivePortrait
  • Java反射机制深度解析与实践应用
  • Oracle递归查询层级及路径
  • leetcode300. 最长递增子序列,动态规划附状态转移方程
  • C语言:字符串函数strcpy
  • Day16-指针2
  • 数据结构(5.5_3)——并查集的进一步优化
  • (回溯) LeetCode 131. 分割回文串
  • 【Linux】阻塞信号|信号原理|深入理解捕获信号|内核态|用户态|sigaction|可重入函数|volatile|SIGCHILD|万字详解
  • 基于Linux对 【进程地址空间】的详细讲解
  • [python]使用Pandas处理多个Excel文件并汇总数据
  • 提升体验:UI设计的可用性原则
  • x264 编码器 SSIM 算法源码分析
  • echarts使图表组件根据屏幕尺寸变更而重新渲染大小
  • 电脑图片损坏打不开怎么办?能修复吗?
  • vue-cli(二)
  • 今日头条的账号id在哪里看(网页版)
  • 单体应用提高性能和高并发处理-合理使用多核处理
  • 基于STM32/GD32的双CAN、一路485开发板
  • 快排/堆排/归并/冒泡/
  • React基础教程(08):state体验
  • Win10 创建新的桌面2,并实现桌面切换
  • MySQL数据库介绍及基础操作
  • 【C语言篇】C语言常考及易错题整理DAY2