leetcode-DP

一、模板

1. 递归（自上而下）

2. 递归 -> 记忆化搜索 （自上而下）

3. 记忆化搜索 -> DP （自下而上）

• 网格问题：求路径, 注意 i , j 边界问题

for(let i = 0;i<n;i++)
  dp[0][i] = 1

for(let i = 0;i<m;i++)
  dp[i][0] = 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]

二、题目

509. 斐波那契数

F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2)

/**
 * 递归  O(2^n) 
 */

function fib(n) {
  if(n === 0) return 0
  if(n === 1) return 1
  return fib(n-1) + fib(n-2)
}

/**
 * 记忆化搜索 O(n) 
 */

const memo = new Array(n + 1).fill(-1)
function  fib(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  if (memo[n] === -1)
    memo[n] = fib(n - 1) + fib(n - 2)
  return memo[n]
}

/**
 * DP —— O(n)
 */

function fib(n) {
  let memo = new Array(n + 1).fill(-1)
  memo[0] = 0
  memo[1] = 1
  for (let i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2]
  }
  return memo[n]
}

70. 爬楼梯

/**
 * 递归
 */

var climbStairs = function (n) {
  return _climb(n)
  
  function _climb(n){
    if (n === 0 || n === 1) return 1
  	return climbStairs(n - 1) + climbStairs(n - 2)
  }
}

/**
 * 每一步1,2,3阶
 */

var climbStairs = function (n) {
  let memo = new Array(n + 1).fill(0)
  memo[0] = 1
  memo[1] = 1
  memo[2] = 2
  for (let i = 3; i <= n; i++)
    memo[i] = memo[i - 1] + memo[i - 2] + memo[i - 3]
  return memo[n]
}

/**
 * 记忆化搜索 
 */

var climbStairs = function (n) {
  const memo = new Array(n + 1).fill(-1)
  return _climb(n)

  function _climb(n) {
    if (n === 0 || n === 1) return 1
    if (memo[n] === -1)
      memo[n] = _climb(n - 2) + _climb(n - 1)
    return memo[n]
  }
};

/**
 * DP
 */

var climbStairs = function (n) {
  const memo = new Array(n + 1).fill(-1)
  memo[0] = 1
  memo[1] = 1
  for(let i = 2;i<=n;i++)
    memo[i] = memo[i-1] + memo[i-2]
  return memo[n]
};

120. 三角形最小路径和

/**
 * 递归
 */

var minimumTotal = function(triangle) {
  return _minimumTotal(triangle,0,0)

  function _minimumTotal(triangle,depth,index){
    if(depth === triangle.length) return 0

    return triangle[depth][index] + Math.min(_minimumTotal(triangle,depth+1,index),_minimumTotal(triangle,depth+1,index+1))
  }
};

/**
 * 记忆化
 */

var minimumTotal = function(triangle) {
  let memo = new Array(triangle.length)
  for(let i = 0;i<memo.length;i++)
    memo[i] = new Array(triangle[i].length).fill(0)

  return _minimumTotal(triangle,0,0)

  function _minimumTotal(triangle,depth,index){
    if(depth === triangle.length) return 0

    if(memo[depth][index] === 0)
      memo[depth][index] = triangle[depth][index] + Math.min(_minimumTotal(triangle,depth+1,index),_minimumTotal(triangle,depth+1,index+1))

    return memo[depth][index]
  }
};

/**
 * DP
 */

var minimumTotal = function (triangle) {
  let n = triangle.length;
  let memo = new Array(n+1);
  for(let i = 0;i< memo.length;i++)
    memo[i] = new Array(n+1).fill(0)

  for (let i = n - 1; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      memo[i][j] = Math.min(memo[i + 1][j], memo[i + 1][j + 1]) + triangle[i][j];
    }
  }
  return memo[0][0];
};

/**
 * DP - 空间优化
 */

var minimumTotal = function (triangle) {
  let n = triangle.length;
  let memo = new Array(n+1).fill(0);

  for (let i = n - 1; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      memo[j] = Math.min(memo[j], memo[j + 1]) + triangle[i][j];
    }
  }
  return memo[0];
};

64. 最小路径和

/**
 * 递归
 */

var minPathSum = function (grid) {
  return dfs(grid, 0, 0)

  function dfs (grid, depth, index) {
    if (depth === grid.length || index === grid[0].length) return 0

    let min
    if (depth + 1 >= grid.length)
      min = dfs(grid, depth, index + 1)
    else if (index + 1 >= grid[0].length)
      min = dfs(grid, depth + 1, index)
    else
      min = Math.min(dfs(grid, depth, index + 1), dfs(grid, depth + 1, index))

    return grid[depth][index] + min
  }
}

/**
 * 记忆化
 */

var minPathSum = function (grid) {
  let n = grid.length
  let memo = new Array(n)
  for (let i = 0; i < memo.length; i++)
    memo[i] = new Array(grid[0].length).fill(0)

  return dfs(grid, 0, 0)

  function dfs (grid, depth, index) {
    if (depth === grid.length || index === grid[0].length) return 0

    let min
    if (depth + 1 >= grid.length)
      min = dfs(grid, depth, index + 1)
    else if (index + 1 >= grid[0].length)
      min = dfs(grid, depth + 1, index)
    else
      min = Math.min(dfs(grid, depth, index + 1), dfs(grid, depth + 1, index))

    if (memo[depth][index] === 0)
      memo[depth][index] = grid[depth][index] + min

    return memo[depth][index]
  }
}

/**
 * DP
 */

var minPathSum = function (grid) {
  let width = grid[0].length,height = grid.length
  for(let i = 1;i<width;i++)
    grid[0][i] += grid[0][i-1]
    
  for(let i = 1;i<height;i++)
    grid[i][0] += grid[i-1][0]

  for(let i = 1;i<height;i++)
    for(let j = 1;j<width;j++)
      grid[i][j] += Math.min(grid[i-1][j],grid[i][j-1])

  return grid[height-1][width-1]
};

343. 整数拆分

/**
 * 递归
 */

var integerBreak = function (n) {
  return dfs(n)

  function dfs(n) {
    if (n === 1)
      return 1

    let res = -1
    for (let i = 1; i < n; i++)
      res = Math.max(res, i * (n - i), i * dfs(n - i))
    return res
  }
};

/**
 * 记忆化
 */

var integerBreak = function (n) {
  const memo = new Array(n + 1).fill(-1)
  return dfs(n)

  function dfs(n) {
    if (n === 1)
      return 1

    if (memo[n] !== -1)
      return memo[n]

    let res = -1
    for (let i = 1; i < n; i++)
      res = Math.max(res, i * (n - i), i * dfs(n - i))
    memo[n] = res
    return res
  }
};

/**
 * DP
 */

var integerBreak = function (n) {
  const memo = new Array(n + 1).fill(-1)
  
  memo[1] = 1
  for(let i = 2;i<=n;i++)
    for(let j = 1;j < i;j++)
      memo[i] = Math.max(memo[i], j * (i-j), j * memo[i-j])
  return memo[n]
};

279. 完全平方数

/**
 * 递归
 */

var numSquares = function(n) {
  return dfs(n)

  function dfs(n){
    if(n === 0) return 0

    let count = Number.MAX_SAFE_INTEGER
    for(let i = 1;i*i <= n;i++)
       count = Math.min(count,dfs(n-i*i)+1)
    return count
  }
};

/**
 * 记忆化
 */

var numSquares = function(n) {
  const memo = new Array(n+1).fill(-1)
  return dfs(n)

  function dfs(n){
    if(n === 0) return 0

    if(memo[n] !== -1) return memo[n]

    let count = Number.MAX_SAFE_INTEGER
    for(let i = 1;i*i <= n;i++)
       count = Math.min(count,dfs(n-i*i)+1)
    memo[n] = count
    return memo[n]
  }
};

/**
 * DP
 */

var numSquares = function (n) {
  const memo = new Array(n + 1).fill(0)
  memo[0] = 0

  for (let i = 1; i <= n; i++) {
    memo[i] = i
    for (let j = 1; i - j * j >= 0; j++)
      memo[i] = Math.min(memo[i], memo[i - j * j] + 1)
  }
  return memo[n]
}

91. 解码方法

/**
 * 递归
 */

var numDecodings = function (s) {
  return dfs(s)

  function dfs (s) {
    if (s === "") return 1

    let count = 0
    if (s[0] !== '0') count += dfs(s.slice(1))
    if (s.length >= 2 && s[0] === '1' || (s[0] === '2' && s[1] >= 0 && s[1] <= 6)) {
      count += dfs(s.slice(2))
    }
    return count
  }
}

/**
 * 记忆化
 */

var numDecodings = function (s) {
  let memo = {}
  return dfs(s)

  function dfs (s) {
    if (s === "") return 1

    if (memo[s]) return memo[s]

    let count = 0
    if (s[0] !== '0') count += dfs(s.slice(1))
    if (s.length >= 2 && s[0] === '1' || (s[0] === '2' && s[1] >= 0 && s[1] <= 6)) {
      count += dfs(s.slice(2))
    }
    memo[s] = count
    return memo[s]
  }
}

/**
 * 记忆化，按顺序
 */

var numDecodings = function (s) {
  let memo = {}
  return dfs(0)

  function dfs (i) {
    if (i === s.length) return 1

    if (memo[i]) return memo[i]

    let count = 0
    if (s[i] !== '0') count += dfs(i+1)
    if (i < s.length-1 && s[i] === '1' || (s[i] === '2' && s[i+1] >= 0 && s[i+1] <= 6)) {
      count += dfs(i+2)
    }
    memo[i] = count
    return memo[i]
  }
}

/**
 * DP
 */

var numDecodings = function (s) {
  if(s.length === 0) return 0
  let memo = new Array(s.length+1).fill(0)
  memo[0] = 1
  memo[1] = s[0] === '0' ? 0 : 1
  for(let i = 2;i<=s.length;i++){
    if(s[i-1] !== "0") 
      memo[i] += memo[i-1]
    if(s[i-2] === '1' || (s[i-2] === "2" && s[i-1] >=0 && s[i-1] <=6)) 
      memo[i] += memo[i-2]
  }
  return memo[s.length]
}

62. 不同路径

/**
 * 递归
 */

var uniquePaths = function(m, n) {
  return dfs(0,0,m,n)

  function dfs(i,j,m,n){
    if(i > m-1 || j > n-1) return 0
    if(i === m-1 && j === n-1) return 1
    return dfs(i+1,j,m,n) + dfs(i,j+1,m,n)
  }
};

/**
 * 记忆化
 */

var uniquePaths = function(m, n) {
  let memo = new Array(m).fill(0).map(()=>new Array(n).fill(0))
  return dfs(0,0,m,n)

  function dfs(i,j,m,n){
    if(i > m-1 || j > n-1) return 0
    if(i === m-1 && j === n-1) return 1

    if(memo[i][j] === 0)
      memo[i][j] = dfs(i+1,j,m,n) + dfs(i,j+1,m,n)
    return memo[i][j]
  }
};

/**
 * DP
 */

var uniquePaths = function(m, n) {
  const dp = new Array(m).fill(0).map(()=>new Array(n).fill(0))

  for(let i = 0;i<n;i++)
    dp[0][i] = 1

  for(let i = 0;i<m;i++)
    dp[i][0] = 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]
};

63. 不同路径 II

/**
 * 递归
 */

var uniquePathsWithObstacles = function (obstacleGrid) {
  let height = obstacleGrid.length,
    width = obstacleGrid[0].length
  return dp(0, 0, obstacleGrid)

  function dp (i, j, obstacleGrid) {
    if (i > height - 1 || j > width - 1 || obstacleGrid[i][j] === 1)
      return 0
    if (i === height - 1 && j === width - 1)
      return 1
    return dp(i + 1, j, obstacleGrid) + dp(i, j + 1, obstacleGrid)
  }
}

/**
 * 记忆化
 */

var uniquePathsWithObstacles = function (obstacleGrid) {
  let height = obstacleGrid.length,
    width = obstacleGrid[0].length
  let memo = new Array(height).fill(0).map(() => new Array(width).fill(0))
  return dp(0, 0, obstacleGrid)

  function dp(i, j, obstacleGrid) {
    if (i > height - 1 || j > width - 1 || obstacleGrid[i][j] === 1) 
      return 0
    if (i === (height - 1) && j === (width - 1)) 
      return 1

    if(memo[i][j]) 
      return memo[i][j]

    memo[i][j] = dp(i + 1, j, obstacleGrid) + dp(i, j + 1, obstacleGrid)
    return memo[i][j]
  }
};

/**
 * DP
 */

var uniquePathsWithObstacles = function (obstacleGrid) {
  let height = obstacleGrid.length,
    width = obstacleGrid[0].length
  let memo = new Array(height).fill(0).map(() => new Array(width).fill(0))
  for(let i = 0; i<height && obstacleGrid[i][0] === 0;i++)
    memo[i][0] = 1
  for(let i = 0; i<width && obstacleGrid[0][i] === 0;i++)
    memo[0][i] = 1
  
  for(let i = 1;i<height;i++)
    for(let j = 1;j<width;j++)
      if(obstacleGrid[i][j] === 0)
        memo[i][j] = memo[i-1][j] + memo[i][j-1]
  return memo[height-1][width-1]
};

1143. 最长公共子序列

/**
 * 记忆化
 */

var longestCommonSubsequence = function (text1, text2) {
  let memo = new Array(text1.length).fill(0).map(() => new Array(text2.length).fill(0))
  return dfs(text1.length - 1, text2.length - 1)

  function dfs(i, j) {
    if (i === -1 || j === -1)
      return 0

    if(memo[i][j]) return memo[i][j]

    if (text1[i] === text2[j])
      memo[i][j] = 1 + dfs(i - 1, j - 1)
    else
      memo[i][j] = Math.max(
        dfs(i - 1, j),
        dfs(i, j - 1),
        dfs(i - 1, j - 1)
      )

    return memo[i][j]
  }
};

/**
 * DP
 */

var longestCommonSubsequence = function(text1, text2) {
  if(!text1.length || !text2.length) return 0

  let m = text1.length
  let n = text2.length
  let dp = new Array(m+1).fill(0).map(()=>new Array(n+1).fill(0))

  for(let i = 1;i<m+1;i++)
    for(let j = 1;j<n+1;j++){
      if(text1[i-1] === text2[j-1])
        dp[i][j] = dp[i-1][j-1] + 1
      else
        dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
    }
  
  return dp[m][n]
};

198. 打家劫舍

/**
 * 递归
 */

var rob = function (nums) {
  return dfs(nums, 0)

  function dfs(nums, index) {
    if (index > nums.length - 1)
      return 0

    let res = -1
    for (let i = index; i <= nums.length - 1; i++)
      res = Math.max(res, nums[i] + dfs(nums, i + 2))
    return res
  }
};

/**
 * 记忆化搜索
 */

var rob = function (nums) {
  const memo = new Array(nums.length).fill(-1)
  return dfs(nums, 0)

  function dfs(nums, index) {
    if (index > nums.length - 1)
      return 0

    if (memo[index] !== -1)
      return memo[index]

    let res = -1
    for (let i = index; i <= nums.length - 1; i++)
      res = Math.max(res, nums[i] + dfs(nums, i + 2))
    memo[index] = res
    return res
  }
};

/**
 * DP
 */

var rob = function (nums) {
  const memo = new Array(nums.length).fill(-1)
  const n = nums.length
  memo[n - 1] = nums[n - 1]
  for (let i = n - 2; i >= 0; i--)
    for (let j = i; j < n; j++)
      memo[i] = Math.max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0))
  return memo[0]
};

01背包

/**
 * 记忆化
 */

var knapsack01 = (w, v, C) => {
  let memo = new Array(w.length).fill(0).map(() => new Array(C + 1).fill(-1))
  return bestValue(w, v, 1, C)

  function bestValue (w, v, index, c) {
    if (index >= w.length || c <= 0)
      return 0

    if (memo[index][c] !== -1) return memo[index][c]

    let res = bestValue(w, v, index + 1, c) // no pick
    if (c >= w[index])
      res = Math.max(res, v[index] + bestValue(w, v, index + 1, c - w[index]))
    memo[index][c] = res
    return res
  }
}

/**
 * DP
 */

var knapsack01 = (w, v, C) => {
  let memo = new Array(w.length).fill(0).map(() => new Array(C + 1).fill(-1))

  for (let i = 0; i < w.length; i++)
    memo[i][0] = 0
  for (let i = 0; i <= C; i++)
    memo[0][i] = i >= w[0] ? v[0] : 0

  for (let i = 1; i < w.length; i++)
    for (let j = 1; j <= C; j++) {
      memo[i][j] = memo[i - 1][j]
      if (j >= w[i])
        memo[i][j] = Math.max(memo[i][j], v[i] + memo[i - 1][j - w[i]])
    }

  return memo[w.length - 1][C]
}

• [ ] 213
• [ ] 337
• [ ] 309