算法:从某一点出发到另一点有多少种走法(不走冤枉路)
2020-05-12 本文已影响0人
金星show

单位节点都是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);
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)
}