暑期算法 第六题
题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
来源:知乎
题解
1 |
|
题析
这是一道动态规划题,做此类题型必须抓住三个要点:
定义数组元素的含义
定义 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数组定义、关系式和初始条件。
暑期算法 第六题
http://lafish.fun/sqsf-6/