一,问题描述
有个小孩上楼梯,共有N阶楼梯,小孩一次可以上1阶,2阶或者3阶。走到N阶楼梯,一共有多少种走法?
二,问题分析
DP之自顶向下分析方式:
爬到第N阶楼梯,一共只有三种情况(全划分,加法原理),从第N-1阶爬1阶到第N阶;从第N-2阶爬2阶到第N阶;从第N-3爬3阶到第N阶。
故:way(N)=way(N-1)+way(N-2)+way(N-3)
这与求Fib数列非常相似,当然,其他类似的问题也可以这样求解。
初始条件:
way(1)=1
way(2)=2
way(3)=4
这里解释一下way(3)=4。爬到第3层一共有4种方式:每次爬一层,1+1+1=3;先爬一层,再爬二层,1+2=3;先爬二层,再爬一层,2+1=3;一次性爬三层。
三,代码实现
public class WaysOfLadder { public static int ways(int n){
if(n <= 0)
throw new IllegalArgumentException();
return waysLadder(n);
} //递归算法爬上第n阶楼梯一共需要多少种方式
private static int waysLadder(int n){
assert n > 0;
//base condition
if(n == 1)
return 1;
if(n == 2)
return 2;
if(n == 3)
return 4;
else
return waysLadder(n-1) + waysLadder(n - 2) + waysLadder(n - 3);
} //dp
public static int ways_dp(int n){
if(n <= 0)
throw new IllegalArgumentException(); int pre_1 = 1;
int pre_2 = 2;
int pre_3 = 4;
int res = 0;
for(int i = 4; i <= n; i++)
{
res = pre_1 + pre_2 + pre_3;
pre_1 = pre_2;
pre_2 = pre_3;
pre_3 = res;
}
return res;
} public static void main(String[] args) {
int n = 32;
System.out.println(ways_dp(n));
System.out.println(ways(n));
}
}
上面代码清晰地对比了DP实现与递归实现的方式。DP是用三个变量保存当前计算的结果,当计算下一个结果时,先“查表”再计算。而递归则是使用三个递归函数调用,递归函数调用计算了大量的重叠的子问题,每次递归调用都要压栈、出栈。递归的时间复杂度为O(3^N),而DP的时间复杂度为O(N)
类似的思想,还有计算杨辉三角的公式:C(n,r)=C(n-1,r) + C(n-1,r-1)具体可参考:
只不过杨辉三角的计算公式有两个参数而已。
另外,相关问题可参考:组合问题与动态规划的联系之应用