算法:从某一点出发到另一点有多少种走法(不走冤枉路)

2020-05-12  本文已影响0人  金星show
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);
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)
}

上一篇 下一篇

猜你喜欢

热点阅读