赤峰做网站的,logo设计软件在线制作,海口专业做网站,在线做网站怎么做背景
今天在做Leetcode题目时#xff0c;做到了一道经典的动态规划问题#xff1a;爬楼梯#xff0c;题目的大致意思很简单#xff0c;有个小孩正在上楼梯#xff0c;楼梯有n阶台阶#xff0c;小孩一次可以上1阶、2阶或3阶。实现一种方法#xff0c;计算小孩有多少种上…背景
今天在做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阶台阶的方法数到达第4阶台阶你可以先上1阶然后剩下的是上3阶台阶的方法数即 dp[3]。 上2阶台阶的方法数到达第4阶台阶你可以先上2阶然后剩下的是上2阶台阶的方法数即 dp[2]。 上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[n−1]dp[n−2]dp[n−3];
这个方程表示到达第 ( n ) 阶台阶的方法数是到达第 ( n-1 ) 阶、( n-2 ) 阶和 ( n-3 ) 阶台阶的方法数之和。这里没有重复计算任何情况每个情况都被独立考虑了一次。
总结
之前的思考过程尝试将问题分解为多个部分这是一个很好的方法但是在合并这些部分时需要确保没有重复计算任何情况。正确的方法是使用动态规划确保每一步都是基于前几步的结果并且没有重复或遗漏。
