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?
A:
就是简单的DP问题
public class Solution { public int climbStairs(int n) { //DP if(n ==1 || n ==2) return n; int[] A = new int[n]; A[0] = 1; A[1] = 2; for(int i=2;i<n;i++) A[i] = A[i-1]+A[i-2]; return A[n-1]; } }
Mistakes:
1: 哎,刚开始,竟然,连n=2的情况,都能弄错, SB啊,真是~~~~~
应该是基于n=1 n=2的情况来考虑, 而不是因为,有了n=0 ,n =1 的情况了,就可以作为基本情况了。-----------------------------这个是base case 没有考虑清楚。
Learned:
No comments:
Post a Comment