/*

x x      x
x x      x(1,2)
x x(2,1) x(2,2)

到(2,2)的所有路径 = 到(1,2)的所有路径 + 到(2,1)的所有路径

*/



/*

[1,1]: 1

[1,2]: 1
[1,3]: 1

[2,1]: 1
[3,1]: 1

[2,2]: 2

x x
x x

注意：坐标表示需要x,y都-1

*/

const numberOfPath = (row, col) => {
  const dp = []

  for (let i = 0; i < row; i++) {
    dp[i] = []

    for (let j = 0; j < col; j++) {
      if (i === 0 || j === 0) dp[i][j] = 1

      if (i > 0 && j > 0) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      }
    }
  }

  console.log(dp)

  return dp[row - 1][col - 1]
}

var re = numberOfPath(3, 3)
console.log(re)

var re = numberOfPath(1, 1)
console.log(re)

var re = numberOfPath(2, 3)
console.log(re)

var re = numberOfPath(2, 4)
console.log(re)

var re = numberOfPath(4, 4)
console.log(re)