有一座高10级台阶的楼梯，从下往上走，一次只能向上1级或2级台阶，一共有多少种走法？
结题思路：
1.递归：时间复杂度 2^n
2.备忘录算法：时间复杂度n
3.动态规划：时间复杂度n
// 1.递归：时间复杂度 2^n
private static int stepCount(int count) {
if (count < 1) {
return 0;
}
if (count <= 2) {
return count;
}
return stepCount(count - 1) + stepCount(count - 2);
}
//2.备忘录算法：时间复杂度n
private static int stepCount2(int count, Map<Integer,Integer> map) {
if (count<1){
return 0;
}
if (count<=2){
return count;
}
if(map.containsKey(count)){
return map.get(count);
}else {
int value=stepCount2(count-1,map)+stepCount2(count-2,map);
map.put(count,value);
return value;
}
}
//3.动态规划：时间复杂度n
private static int stepCount3(int count) {
if (count<1){
return 0;
}
if (count<=2){
return count;
}
int left=1,right=2,temp=0;
for (int i = 3; i <=count ; i++) {
temp=left+right;
left=right;
right=temp;
}
return temp;
}
注：以上解法出自微信公众号《程序员小灰》.
