Liber's Blog

欢迎访问Liber的私人博客，这是最新的一篇内容

动态规划

计算到从起点（左上角）到终点（右下角）的路径数：


/*

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)

从递归到动态规划的转变，核心是从一种自顶向下的解决问题的方式（递归）转变为自底向上的方式（动态规划），通过保存中间结果来避免重复计算，从而显著提高算法效率。这种转变涉及到对问题的结构性理解，发现最优子结构，定义状态和状态转移方程，并实现有效的计算和存储方式。

动态规划的核心思想是利用子问题的解来构建原问题的解，而这通常需要状态转移方程。