image.png
单位节点都是1；
数学公式为：先算单个节点的路数，进而往上叠加，对角路数为旁边两个点的线路数量之和；
//从某一点到另一点有多少种走法(不重复)
$a = '0,0'; //原点
$b = '3,2'; //目标点
list($xMax,$yMax) = explode(',',$b);
$step = 1;
for($x=0;$x<=$xMax;$x++){
for($y=0;$y<=$yMax;$y++){
$key = $x.','.$y;
if ($x==0 || $y==0) {
$data[$key] = 1;
} else {
$xTmp = $x-1;
$key_x = $xTmp.','.$y;
$yTmp = $y-1;
$key_y = $x.','.$yTmp;
$data[$key] = $data[$key_x] + $data[$key_y];
}
}
}
var_dump($data);
function zoutu($x,$y){//动态规划
for($i=0;$i<=$x;$i++){
for($j=0;$j<=$y;$j++){
if($i==0 || $j==0){
$dp[$i][$j] = 1;
}else{
$dp[$i][$j] = 0;
}
}
}
for($i=1;$i<=$x;$i++){
for($j=1;$j<=$y;$j++){
$dp[$i][$j] = $dp[$i-1][$j] + $dp[$i][$j-1];
}
}
return $dp[$x][$y];
}
$x = 3;
$y = 2;
var_dump(zoutu($x,$y));
array(12) {
["0,0"]=>
int(1)
["0,1"]=>
int(1)
["0,2"]=>
int(1)
["1,0"]=>
int(1)
["1,1"]=>
int(2)
["1,2"]=>
int(3)
["2,0"]=>
int(1)
["2,1"]=>
int(3)
["2,2"]=>
int(6)
["3,0"]=>
int(1)
["3,1"]=>
int(4)
["3,2"]=>
int(10)
}
