有一座高10級(jí)臺(tái)階的樓梯唠倦，從下往上走玖像，一次只能向上1級(jí)或2級(jí)臺(tái)階匪燕，一共有多少種走法摸吠？
結(jié)題思路：
1.遞歸：時(shí)間復(fù)雜度 2^n
2.備忘錄算法：時(shí)間復(fù)雜度n
3.動(dòng)態(tài)規(guī)劃：時(shí)間復(fù)雜度n
// 1.遞歸：時(shí)間復(fù)雜度 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.備忘錄算法：時(shí)間復(fù)雜度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.動(dòng)態(tài)規(guī)劃：時(shí)間復(fù)雜度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;
}
注：以上解法出自微信公眾號(hào)《程序員小灰》.
