动态规划

• 计算到达某一个格子的路径数目有多少就是对格子上方和左方的格子数目求和
• 第一行和第一列都是只有一种路径
• 求m*n就是对应求每个格子的和

/**
  * 
  * @param m int整型 
  * @param n int整型 
  * @return int整型
  */
function uniquePaths( m ,  n ) {
    // write code here
    let dp=[]
    //第一列格子路径都为1
    for(let i=0;i<m;i++){
        dp[i]=new Array(n)
        dp[i][0]=1
    }
    //第一行格子路径都为1
    for(let i=0;i<n;i++){
        dp[0][i]=1
    }
  	//求和
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}
module.exports = {
    uniquePaths : uniquePaths
};