动态规划问题

面试时被问道一个问题:

一个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;

}

---