算法之杨辉三角

先对杨辉三角有个印象

求 第 h 行 第 r 列的数值

返回的结果：

使用递归1：第 100 行第 4 列值是： 156849 ，共计算 387 次，耗时 0.001 s
不用递归2：第 100 行第 4 列值是： 156849 ，共计算 292 次，耗时 0.001 s
不用递归3：第 100 行第 4 列值是： 156849 ，共计算 389 次，耗时 0.003 s

使用递归1：第 1000 行第 4 列值是： 165668499 ，共计算 3987 次，耗时 0.025 s
不用递归2：第 1000 行第 4 列值是： 165668499 ，共计算 2992 次，耗时 0.004 s
不用递归3：第 1000 行第 4 列值是： 165668499 ，共计算 3989 次，耗时 0.022 s

使用递归1：第 5000 行第 100 列值是： 624014247245299026906445998123558217870956092980555531377768115986897461531075814054704987026416324300946857745465985368470695552826369735898524891324219910107723427537989045846838371991032479953737061920407552 ，共计算 490099 次，耗时 0.522 s
不用递归2：第 5000 行第 100 列值是： 624014247245299026906445998123558217870956092980555531377768115986897461531075814054704987026416324300946857745465985368470695552826369735898524891324219910107723427537989045846838371991032479953737061920407552 ，共计算 485296 次，耗时 0.240 s
不用递归3：第 5000 行第 100 列值是： 624014247245299026906445998123558217870956092980555531377768115986897461531075814054704987026416324300946857745465985368470695552826369735898524891324219910107723427537989045846838371991032479953737061920407552 ，共计算 490197 次，耗时 0.420 s

注：递归的方式之所以要维护一个数组，是因为避免重复执行递归操作；

可以得出结论，第二种方法和第一、三种虽然循环次数并没有少一个数量，但使用内存更少（只使用一个一维数组），所以计算所花费的时间少很多。

function getMillisecond() {
    list($s1, $s2) = explode(' ', microtime());
    return (float)sprintf('%.03f', (floatval($s1) + floatval($s2)));
}
function yanghui($h,$r){
    $rr = $r;
    if($r > $h){
        die("\$r = $r 不能大于 \$h = $h");
    }
    if($r > ceil($h/2)){
        $rr = $h+1-$r;
    }
    echo "使用递归1：";
    compute($h,$r,'yanghui1');
    echo "不用递归2：";
    compute($h,$r,'yanghui2');
    echo "不用递归3：";
    compute($h,$r,'yanghui3');
}
function compute($h,$r,$fun){
    $count = 0;
    $time = getMillisecond();
    if($fun == 'yanghui1'){
        $arr = [];
        $v = $fun($h,$r,$count,$arr);
    }else{
        $v = $fun($h,$r,$count);
    }
    $v = number_format($v,0,'.','');
    $time = sprintf('%.03f',getMillisecond() - $time);
    echo "第 $h 行第 $r 列值是： $v ，共计算 $count 次，耗时 $time s\r\n";
}
function yanghui1($h,$r,&$count,&$arr){
    if(!isset($arr[$h])){
        $arr[$h] = [];
    }
    if(!isset($arr[$h][$r])){
        $count ++;
        if($r == 1 || $r == $h){
            $arr[$h][$r] = 1;
        }else{
            $arr[$h][$r] = yanghui1($h-1,$r,$count,$arr)+yanghui1($h-1,$r-1,$count,$arr);
        }
    }
    return $arr[$h][$r];
}
function yanghui2($h,$r,&$count){
    $a = [];
    $a[2] = $a[1] = 1;
    $border = ($h+1-$r);
    for($i=3;$i<=$h;$i++){
        $pre = $a;
        if($i <= $border){
            for($j = 2; $j <= min([$i,$r]); $j++){
                $a[$j] = $pre[$j-1]+$pre[$j];
                $count ++ ;
            }
        }else{
            for($j=max([($i-$border),2]);$j <= $r; $j++){
                $a[$j] = $pre[$j-1]+$pre[$j];
                $count ++;
            }
        }
    }
    return $a[$r];
}
function yanghui3($h,$r,&$count){
    $border = ($h+1-$r);
    $arr = [];
    $arr[1][1] = 1;
    if($h >= 2){
        for($i=2;$i<=$h;$i++){
            if($i <= $border){
                for($j = 1; $j <= min([$i,$r]); $j++){
                    $arr[$i][$j] = $arr[$i-1][$j-1]+$arr[$i-1][$j];
                    $count ++ ;
                }
            }else{
                for($j=max([($i-$border),2]);$j <= $r; $j++){
                    $arr[$i][$j] = $arr[$i-1][$j-1]+$arr[$i-1][$j];
                    $count ++;
                }
            }
        }
    }
    return $arr[$h][$r];
}
$h = $_GET['h']?$_GET['h']:6;
$r = $_GET['r']?$_GET['r']:3;
yanghui($h,$r);