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

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)
}