动态规划

// 这里我得说一下 在做动态规划的时候，我犯了一个巨大的错误，我想着用对象来代替数组存储，对象的下标为二维数组的下标，计算会出现问题
// 1.动态规划：利用历史记录避免进行重复计算，历史记录一般使用一维数组或者二维数组来保存
// 定义数组的含义：dp[i]是代表什么意思
// 找出数组元素之间的关系式：利用历史数据推出新的元素值
// 找出初始值

// 1.一只青蛙一次可以跳1级台阶或者2级台阶，求该青蛙跳上n级台阶共有多少种跳法
// 根据问题定义dp[i]:跳上i级台阶一共有dp[i]种跳法 =》 dp[n] = dp[n-2] + dp[n-1]
function stepsMethods(n) {
  if(n=== 0) return 1
  let nums = []
  nums[1] = 1
  nums[2] = 2
  for(let i = 3; i <= n; i++) {
    nums[i] = (nums[i-1] + nums[i-2])% 1000000007
  }
  return nums[n] 
}
console.log(stepsMethods(4))

// 2.二维数组的dp: 一个机器人位于一个 m * n的网格左上角（终点在网格的右下角），机器人每次只能向下或者向右移动一步，
// 机器人每次只能向下或者向右移动一步，请问有多少条路径
// 根据问题定义dp[i][j]:当机器人从左上角走到（i，j）一共有dp[i][j]种路径；dp[i][j] = dp[i][j-1] + dp[i-1][j]
function juzhenMethods(m, n) {
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
      f[i][0] = 1;
  }
  for (let j = 0; j < n; j++) {
      f[0][j] = 1;
  }
  for (let i = 1; i < m; i++) {
      for (let j = 1; j < n; j++) {
          f[i][j] = f[i - 1][j] + f[i][j - 1];
      }
  }
  return f[m - 1][n - 1];
}
console.log(juzhenMethods(13,23))

// 3.给定一个包含非负整数的m * n网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和最小
// 举例：
// 输入:
// arr = [
//   [1,3,1],
//   [1,5,1],
//   [4,2,1]
// ]
// 输出: 7
// 解释: 因为路径 1→3→1→1→1 的总和最小
// 定义dp[i][j] = m：到ij格子最小的值位m 则dp[i][j] = min(dp[i][j-1],dp[j-1][i])
function minJuzhenMethods(arr) {
  let a = new Array(arr.length).fill(0).map(()=> new Array(arr[0].length).fill(0))
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr[i].length; j++) {
      a[i][j] = arr[i][j]
    }
  }
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr[i].length; j++) {
      if(i === 0 && j === 0) {
        continue
      }else {
        // 要考虑边界情况，边界的值只能来源于他的左方或者上方
        if(i === 0) {
          a[i][j] = a[i][j-1] + a[i][j]
          continue
        }
        if(j === 0) {
          a[i][j] = a[i-1][j] + a[i][j]
          continue
        }
        a[i][j] = Math.min(a[i-1][j],a[i][j-1]) + a[i][j]
      }
    }
  }

  return a[arr.length-1][arr[0].length-1]
}
let arr = [
  [5,0,1,1,2,1,0,1,3,6,3,0,7,3,3,3,1],
  [1,4,1,8,5,5,5,6,8,7,0,4,3,9,9,6,0],
  [2,8,3,3,1,6,1,4,9,0,9,2,3,3,3,8,4],
  [3,5,1,9,3,0,8,3,4,3,4,6,9,6,8,9,9],
  [3,0,7,4,6,6,4,6,8,8,9,3,8,3,9,3,4],
  [8,8,6,8,3,3,1,7,9,3,3,9,2,4,3,5,1],
  [7,1,0,4,7,8,4,6,4,2,1,3,7,8,3,5,4],
  [3,0,9,6,7,8,9,2,0,4,6,3,9,7,2,0,7],
  [8,0,8,2,6,4,4,0,9,3,8,4,0,4,7,0,4],
  [3,7,4,5,9,4,9,7,9,8,7,4,0,4,2,0,4],
  [5,9,0,1,9,1,5,9,5,5,3,4,6,9,8,5,6],
  [5,7,2,4,4,4,2,1,8,4,8,0,5,4,7,4,7],
  [9,5,8,6,4,4,3,9,8,1,1,8,7,7,3,6,9],
  [7,2,3,1,6,3,6,6,6,3,2,3,9,9,4,4,8]]
console.log(minJuzhenMethods(arr))