动态规划1: 走棋盘问题

有一个8x8的棋盘，一个人从左上角出发，但只能向右或者向下，并且其中有一些障碍点无法经过，问到达右下角有多少中走法？

---

分析

定义f(m, n)为第m行，第n列格子到终点的走法；

找到状态转移方程：
在位置（m, n）处到终点的走法为右边格子的走法+下边格子的走法， 即
f(m, n) = f(m, n-1) + f(m-1, n);
当然还要考虑障碍点，该位置不可能走到，所以到终点的走法为0。综合起来就是

if (isObstacle(m,n)) {
  f(m, n) = 0;
} else {
  f(m, n) = f(m, n-1) + f(m-1, n)
}

具有的初始值：
在最下一条边和最右一条边的点（非终点）上，到终点的走法只有一种，所以此时的f(m, n) 都是1.

这是从起点--> 终点以递推方式来考虑的, 算法时间复杂度为O(2^n)， 也可以通过添加记忆化搜索，将其时间复杂度降低到O(m*n).

自底向上的计算：

function test(m, n){
    let arr = [];
    for(let i = 0; i<m;i++) {
        arr[i] =  []
    }

    for(let i=0; i<m;i++) {
        for(let j=0;j<n;j++) {
            if(i===0 || j ===0) {
                arr[i][j] = 1;
            } else {
                arr[i][j] = arr[i-1][j] + arr[i][j-1];
            }
        }
    }
    return arr[m-1][n-1];
}

---

也可以是终点->起点来循环，此时认为f(m, n)具有初始值的位置是棋盘的右边和下边的点。具体代码如下：

function grid() {
  const row = 8;
  const col = 8;
  //  初始化一个二维数组
  let memo = [];
  for(let x=0; x<row;x++) {
    memo[x] = [];
  }
  // m,n从0开始
  for(let x = row-1; x>=0; x--) {
    for(let y = col-1; y>=0; y--) {
      if(isObstacle(x, y)) {
        memo[x][y] = 0;
      } else if(x === row-1 && y === col-1) { // 这是几个边界值，可以在最初构造二位数组时填入
        memo[x][y] = 0;
      } else if(x === row-1) {
        memo[x][y] = 1 
      } else if(y === col-1) {
        memo[x][y] = 1;
      } else {
        memo[x][y] = memo[x+1][y] + memo[x][y+1];
      }
    }
  }

  return memo[0][0];

  function isObstacle(m, n) {
    if(m === 1 && n===2
      || m===1&& n===6 
      || m===2 && n === 4
      || m === 3 && n === 0
      || m === 3 && n === 2
      || m === 3 && n === 5
      || m === 4 && n === 2
      || m === 5 && n === 3
      || m === 5 && n === 4
      || m === 5 && n === 6
      || m === 6 && n === 1
      || m === 6 && n === 5
    ) {
      return 1;
    } else {
      return 0;
    }
  }
}