暑期算法 第六题

题目

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

来源:知乎

题解

int f( int n ){
    if(n <= 1)
    return n;
    // 先创建一个数组来保存历史数据
    int[] dp = new int[n+1];
    // 给出初始值
    dp[0] = 0;//无意义
  	dp[1] = 1;
    dp[2] = 2;
    // 通过关系式来计算出 dp[n]
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    // 把最终结果返回
    return dp[n];
}

题析

这是一道动态规划题,做此类题型必须抓住三个要点:

定义数组元素的含义

定义 dp[i] 的含义为:跳上一个 i 级的台阶总共有 dp[i] 种跳法

找出数组元素间的关系式

由于情况可以选择跳一级,也可以选择跳两级,所以青蛙到达第 n 级的台阶有两种方式:

  • 一种是从第 n-1 级跳上来

  • 一种是从第 n-2 级跳上来

由于我们是要算所有可能的跳法的,所以有 dp[n] = dp[n-1] + dp[n-2]

找出初始条件

不能通过公式得出的dp[i]值都应该提前给出。

此题关系式中存在n-1与n-2,并且dp[0]是无意义的,所以应该提前给出n=1与n=2的初始值。通过简单计算可知dp[1]=1、dp[2]=2。

题外

这是一道很基础的一维动态规划题,用以入门动态规划算法是不错的。做动态规划算法有三大要点:dp数组定义、关系式和初始条件。