[数据结构与算法]杨辉三角 【动态规划法】

在杨辉三角中，每个数是它左上方和右上方的数的和

输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

算法1

class Solution {

    /**
     * @param Integer $numRows
     * @return Integer[][]
     */
    function generate($numRows) {
        $res = [];
        for($i=0;$i<$numRows;$i++){
            for($j = 0;$j<=$i;$j++ ){
                if($j == 0){
                    $res[$i][$j] = 1;
                }else if($j == $i){
                    $res[$i][$j] = 1;
                }else{
                    $res[$i][$j] = $res[$i-1][$j-1]+$res[$i-1][$j] ;
                }
            }
        }
        return $res;
    }
}

不难看出杨辉三角的规律，每一行的第一列和最后一列由于没有左上或右上节点所以结果都为1，其余直接找出左上和右上接节点相加得出当前结果。