【牛客网】剑指offer编程题:变态跳台阶(C++)
这个题目和之前一篇跳台阶有相似的地方,但是也有不同之处 ,青蛙一次性跳台阶次数有所变化。解题思路:
1、当 number = 1 时,只有一种跳法,dp[1] = 1;
2、当 number = 2 时,有两种跳法, dp[2] = 2;
3、当 number >=3 时:分析青蛙先跳到前面任意一阶,再直接跳到最后一阶的所有情况,还有直接一步跳到最后一阶的情况。
dp[3] = dp[1] + dp[2] + 1;
dp[n] = dp[1] + dp[2] +...+ dp[n-1] + 1;