跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
分析
典型的动态规划
可以通过创建dp[]数组, 而dp[i]为跳上第i层台阶的跳法.
递推公式:
dp[1] = 1;
dp[2] = 2;
dp[i] = dp[i - 1] + dp[i - 2] (i > 2);
进一步分析即菲波那切数列.
代码
1 | public class Solution { |
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
典型的动态规划
可以通过创建dp[]数组, 而dp[i]为跳上第i层台阶的跳法.
递推公式:
dp[1] = 1;
dp[2] = 2;
dp[i] = dp[i - 1] + dp[i - 2] (i > 2);
进一步分析即菲波那切数列.
1 | public class Solution { |
觉得本文不错就点个♥再走吧~