Leetcode日记:70.爬楼梯

爬呀爬呀爬楼梯
爬呀爬呀爬楼梯

题目

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

分析

题目很容易理解,可以选择一次爬两节台阶,也可以爬一节,问究竟有多少种情况(不能忽略顺序)。
这道题和53题的最长子串题有异曲同工之妙,为什么这么说呢?
首先我们来看:
最长字串要对前面计算的子串长度进行更新,在更新的过程中,势必要得出在之前的最长字串是多少
而爬楼梯这道题,同样和前一状态有关,比如爬n节台阶,就会分为两种情况:

  • 在n-1的台阶处爬一层台阶
  • 在n-2的台阶处爬两层台阶

继续向下延伸思考,到达每一次层一共有几种方法这个问题就变成了2个子问题:

  • 到达n-1层台阶有几种方法
  • 到达n-2层台阶有几种方法

动态规划

通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法,这就是动态规划。动态规划常常适用于有重叠子问题和最优子结构性质的问题。我们要明确,动态规划是一种思想,并不是一种具体的算法。

那么适用于动态规划的问题都有哪些特征呢?

  • 最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。
  • 重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

回到原问题

让我们回归这道题,我们总结一下之前分析的结果:

第n个结果=第n-1个结果+第n-2个结果

好的,我们抛开我们熟悉的斐波那契数列不谈(事实上,在只能走1,2节的时候该题的结果就是斐波那契数列。。),我们可以建立一个dp数组,先将1和2两种情况求出来,之后的3、4、…、n+1都可以用前两个已经计算出的子结果得到

这就是我们这道题利用到动态规划的核心算法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}

代码源文件

总结

动态规划问题算法多变,需要多做题熟练掌握这种思想。