暑期算法 第六题

题目

一只青蛙一次可以跳上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数组定义、关系式和初始条件。