面试时被问道一个问题:
一个10阶楼梯 每次只能走1步或者2步,走到头有几种走法
当时第一反应想到的是采用暴力枚举的方案,后面回去研究了一下,这就是一个典型的动态规划问题
1.分析问题
如果最后只剩一级台阶的时候,这时候有两种情况:
1.走1步,从第九阶走 2.走2步,从第8阶走
如果知道从1到9有X钟走法,从1到8有Y种走法,可以得知总共走完需要X+Y种走法,如下图
用F(10)表示走完10阶,F(9)表示走完9阶,F(8)表示走完8阶,那么F(10) = F(9) + F(8)
如上图这就可以分析为一个典型的动态规划问题,动态规划是运筹学中的一个概念,核心思想为大事化小,小事化无
F(1)和F(2)叫做该问题的边界,没有边界的问题是永远得不到结果的,F(N)=F(N-1)+F(N-2)为状态转移公式,F(10)=F(9)+F(8)为最优子结构
function test($n){
if($n<1){
return0;
}
if($n==1){
return1;
}
if($n==2){
return2;
}
$res= test1($n-1)+ test1($n-2);
return$res;
}
function test1($n){
if($n<1){
return0;
}
if($n==1){
return1;
}
if($n==2){
return2;
}
//备忘录算法
static$map=array();
if(in_array($n,$map)){
return$map[$n];
}else{
$res= test1($n-1)+ test1($n-2);
$map[$n]=$res;
return$res;
}
}
function test2($n){
if($n==1){
return1;
}
if($n==2){
return2;
}
$a=1;
$b=2;
$temp=0;
for($i=3;$i<=$n;$i++){
$temp=$a+$b;
$a=$b;
$b=$temp;
}
return$temp;
}
