关于程序员:油管最火的Js动态规划讲解学习笔记

学习笔记

https://www.bilibili.com/vide…

const fib = n => {if (n === 1 || n === 2) return 1
  return fib(n - 1) + fib(n - 2)
}

console.log(fib(6))
console.log(fib(7))
console.log(fib(8))
console.log(fib(50)) // 卡住了

这样的递归会在每次都计算一次, 造成屡次调用屡次

咱们考虑一下如何优化这个过程

思考一个简化版的模型, 咱们的察看一个这样的函数

当咱们递归两次的时候

所以咱们之前的 fib 工夫复杂度是

这真是太蹩脚了

带有记忆的遍历就是 dp

// memoization
// js obj, keys: arg, value returns

// 批改 1 设置 memo 和初始值
const fib = (n, memo = {}) => {
  // 批改 2 查看是否有记忆
  if (n in memo) return memo[n]
  if (n === 1 || n === 2) return 1
  // 批改 3 递归的时候带上咱们的援用
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  return memo[n]
}

console.log(fib(6))
console.log(fib(7))
console.log(fib(8))
console.log(fib(50)) // 很快就出后果了

咱们从极简模式开始剖析

其实这也是一种边界状况

简略状况

每挪动一步, 问题将会简化

所以咱们能够这样想这个问题

具象化的了解就是

const gridTraveler = (m, n) => {if (m === 1 && n === 1) return 1
  if (m === 0 || n === 0) return 0
  return gridTraveler(m - 1, n) + gridTraveler(m, n - 1)
}

console.log(gridTraveler(1,2))
console.log(gridTraveler(3,2))
console.log(gridTraveler(3,3))
console.log(gridTraveler(18,18))

const gridTraveler = (m, n, memo = {}) => {const key = `${m}+${n}`
  if (key in memo) return memo[key]
  if (m === 1 && n === 1) return 1
  if (m === 0 || n === 0) return 0
  memo[key] = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo)
  return memo[key]
}

console.log(gridTraveler(1, 2))
console.log(gridTraveler(3, 2))
console.log(gridTraveler(3, 3))
console.log(gridTraveler(18, 18))

胜利最小后果和失败最小后果

逆向思维: 求和到定值 -> 应用定值遍历数组减到 0

我的解法

const canSum = (targetSum, numbers) => {if (targetSum === 0) return true
  if (targetSum < 0) return false

  let remainder
  for (let num of numbers) {remainder = remainder || canSum(targetSum - num, numbers)
  }
  return remainder
}

console.log(canSum(7, [3, 2]))
console.log(canSum(7, [4, 2]))
console.log(canSum(7, [5, 6, 2]))
console.log(canSum(300, [7, 14]))

视频解法

const canSum = (targetSum, numbers) => {if (targetSum === 0) return true
  if (targetSum < 0) return false

  for (let num of numbers) {if (canSum(targetSum - num, numbers)) return true
  }
  return false
}

视频解法递归次数更少

const canSum = (targetSum, numbers, memo = {}) => {if (targetSum in memo) return memo[targetSum]
  if (targetSum === 0) return true
  if (targetSum < 0) return false

  for (const num of numbers) {memo[targetSum] = canSum(targetSum - num, numbers, memo)
    if (memo[targetSum]) return true
  }
  return false
}

console.log(canSum(7, [3, 2]))
console.log(canSum(7, [4, 2]))
console.log(canSum(7, [5, 6, 2]))
console.log(canSum(300, [7, 14]))

const howSum = (targetSum, numbers) => {if (targetSum === 0) return []
  if (targetSum < 0) return null

  for (const num of numbers) {
    const remainder = targetSum - num
    const remainderResult = howSum(remainder, numbers)
    if (remainderResult !== null) return [...remainderResult, num]
  }
  return null
}

console.log(howSum(7, [3, 2]))
console.log(howSum(7, [4, 2]))
console.log(howSum(7, [5, 6, 2]))
console.log(howSum(300, [7, 14]))

const howSum = (targetSum, numbers, memo = {}, path = []) => {if (targetSum in memo) return memo[targetSum]
  if (targetSum === 0) return []
  if (targetSum < 0) return null

  for (const num of numbers) {
    const remainder = targetSum - num
    const remainderResult = howSum(remainder, numbers, memo) 
    if (remainderResult !== null) {memo[targetSum] = [...remainderResult, num]
      return memo[targetSum]
    }
  }
  memo[targetSum] = null // 不可达也须要记录
  return memo[targetSum]
}

console.log(howSum(7, [3, 2]))
console.log(howSum(7, [4, 2]))
console.log(howSum(7, [4, 3, 2]))
console.log(howSum(7, [5, 6, 2]))
console.log(howSum(300, [7, 14]))

想好进口, 边界条件, 失败胜利条件
调用递归函数的时候要假如递归函数能获取到你想要的后果

const bestSum = (targetSum, numbers, lastBest) => {if (targetSum === 0) return []
  if (targetSum < 0) return null

  let shortestCombination = null

  for (const num of numbers) {
    const remainder = targetSum - num
    const remainderCombination = bestSum(remainder, numbers)
    if (remainderCombination !== null) {const combination = [...remainderCombination, num]
      if (
        shortestCombination === null ||
        combination.length < shortestCombination.length
      )
        shortestCombination = combination
    }
  }

  return shortestCombination
}

console.log(bestSum(7, [1, 3, 2, 7])) // [7]
console.log(bestSum(7, [1, 4, 2])) // [2,4,1]
console.log(bestSum(7, [1, 4, 3, 2])) // [3,4]
console.log(bestSum(7, [1, 5, 6, 2])) // [6, 1]
console.log(bestSum(100, [1, 2, 3, 14]))

const bestSum = (targetSum, numbers, memo = {}) => {if (targetSum in memo) return memo[targetSum]
  if (targetSum === 0) return []
  if (targetSum < 0) return null

  let shortestCombination = null

  for (const num of numbers) {
    const remainder = targetSum - num
    const remainderCombination = bestSum(remainder, numbers, memo)
    if (remainderCombination !== null) {const combination = [...remainderCombination, num]
      if (
        shortestCombination === null ||
        combination.length < shortestCombination.length
      )
        shortestCombination = combination
    }
  }

  memo[targetSum] = shortestCombination
  return memo[targetSum]
}

console.log(bestSum(7, [1, 3, 2, 7])) // [7]
console.log(bestSum(7, [1, 4, 2])) // [2,4,1]
console.log(bestSum(7, [1, 4, 3, 2])) // [3,4]
console.log(bestSum(7, [1, 5, 6, 2])) // [6, 1]
console.log(bestSum(100, [1, 2, 3, 5, 10, 40])) //[40, 40, 10, 10]

很显然, 这和 canSum 是一类问题

寻找这个问题的边界条件, 也就是递归终止条件, 一直缩小字符的长度, 直到为空即可, 失败就是残余的字符的子字符不在 wordbank 外面

问题来了 1. 如何存储曾经匹配的字符? 如何判断以后字符曾经不能再被匹配了?

每次胜利匹配后, 就宰割字符串, 顺次查问取后果的和运算后果, 当字符串是空为胜利后果, 循环完了没有符合条件, 有一个宰割后的子串不能满足状况的是失败后果

const canConstruct = (target, wordBank) => {if (target === '') return true

  for (const word of wordBank) {if (target.indexOf(word) !== -1) {
      return target
        .split(word, 2)
        .reduce((pre, targetStr) => pre && canConstruct(targetStr, wordBank),
          true
        )
    }
  }
  return false
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'Dog', 'Vs']))

认真想一下, 这个有一个很大的问题, 就是程序匹配到第一个宰割点后间接返回, 没有查看第二个宰割点是否还能满足条件

console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))// 本该为 true, 输入 false

所以作出这样的批改

const canConstruct = (target, wordBank) => {if (target === '') return true
  return wordBank.reduce((pre, word) => {if (target.indexOf(word) !== -1) {
      return (
        pre ||
        target
          .split(word, 2)
          .reduce((pre, targetStr) => pre && canConstruct(targetStr, wordBank),
            true
          )
      )
    }
    return pre
  }, false)
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))

这样就能够解决那个问题了, 然而这样又有一个不太好的中央就是, 不能见好就收, 找到 pre 是 true 的时候就可停下来了, 所以, 咱们能够应用 some 来代替, some 在返回 true 的时候会进行循环, 相似的 every 将会在返回 false 的时候跳出循环.

当然还能够应用 throw+trycatch 实现终止循环, 然而那样太奇怪了, 很反模式, 不过我还是实现了一下

some/every 优化版

const canConstruct = (target, wordBank) => {if (target === '') return true
  console.log(target, wordBank)
  return wordBank.some(
    word =>
      target.indexOf(word) !== -1 &&
      target.split(word, 2).every(subStr => canConstruct(subStr, wordBank))
  )
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))

try-catch 版

看着就恶心

const canConstruct = (target, wordBank) => {if (target === '') return true
  try {return wordBank.reduce((pre, word) => {if (pre === true) throw new Error(true)
      if (target.indexOf(word) !== -1) {
        return (
          pre ||
          target
            .split(word, 2)
            .reduce((pre, targetStr) => pre && canConstruct(targetStr, wordBank),
              true
            )
        )
      }
      return pre
    }, false)
  } catch (e) {// console.log(typeof e.message)
    // 留神这里会把 boolean 转成 string, 间接 return ture 就好了
    return true
  }
  return false
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))

咱们能够从左到右顺次查看是否是子串, 这样就能够省很多事件, 而且递归的时候能够不须要查看两边的是否都满足

这体现了一种转换的思路

const canConstruct = (target, wordBank) => {if (target === '') return true

  for (const word of wordBank) {if (target.indexOf(word) === 0) {const suffix = target.slice(word.length)
      if (canConstruct(suffix, wordBank) === true) return true
    }
  }

  return false
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))

之前忘了压力测试的用例了, 不必想, 必定都跑不完

console.log(
  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
    'e',
    'ee',
    'eee',
    'eeee'
  ])
)

啊这, 过压力测试用例的时候, 发现: 应用 split 将会把每个 e 都宰割掉, 所以会失去 ['',''] 的后果, 所以会错

所以须要实现一个只宰割一次的函数

const canConstruct = (target, wordBank) => {if (target === '') return true
  return wordBank.some(
    word =>
      target.indexOf(word) !== -1 &&
      splitOnce(target, word).every(subStr => canConstruct(subStr, wordBank))
  )
}

// 只宰割一次的函数
const splitOnce = (str, sign) => {const index = str.indexOf(sign)
  if (index === -1) return [str]
  return [str.slice(0, index), str.slice(index + sign.length)]
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))
console.log(
  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
    'ef',
    'eeeeeeeeeee'
  ])
)
console.log(
  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
    'e',
    'ee',
    'eee',
    'eeeeeeeeeee'
  ])
)

const canConstruct = (target, wordBank, memo = {}) => {if (target in memo) return memo[target]
  if (target === '') return true
  memo[target] = wordBank.some(
    word =>
      target.indexOf(word) !== -1 &&
      splitOnce(target, word).every(subStr =>
        canConstruct(subStr, wordBank, memo)
      )
  )
  return memo[target]
}

const splitOnce = (str, sign) => {const index = str.indexOf(sign)
  if (index === -1) return [str]
  return [str.slice(0, index), str.slice(index + sign.length)]
}

const canConstruct = (target, wordBank, memo = {}) => {if (target in memo) return memo[target]
  if (target === '') return true

  memo[target] = false
  for (const word of wordBank) {if (target.indexOf(word) === 0) {const suffix = target.slice(word.length)
      if (canConstruct(suffix, wordBank, memo) === true){memo[target] = true
        return true
      }
    }
  }

  return memo[target]
}

const countConstruct = (target, wordBank, counter = 0) => {if (target === '') return counter + 1
  for (const word of wordBank) {if (target.indexOf(word) === 0) {const suffix = target.slice(word.length)
      counter = countConstruct(suffix, wordBank, counter)
    }
  }

  return counter
}

const countConstruct = (target, wordBank) => {if (target === '') return 1
  let counter = 0
  for (const word of wordBank)
    if (target.indexOf(word) === 0)
      counter += countConstruct(target.slice(word.length), wordBank)

  return counter
}

const countConstruct = (target, wordBank, memo = {}) => {if (target in memo) return memo[target]
  if (target === '') return 1
  let counter = 0
  for (const word of wordBank)
    if (target.indexOf(word) === 0)
      counter += countConstruct(target.slice(word.length), wordBank, memo)

  memo[target] = counter
  return memo[target]
}

我感觉我曾经挺纯熟了

const allConstruct = (target, wordBank) => {const path = []
  helper(target, wordBank, [], path)
  return path
}

const helper = (target, wordBank, currentPath = [], path = []) => {if (target === '' && currentPath.length !== 0) {path.push([...currentPath])
  }

  for (const word of wordBank) {if (target.indexOf(word) === 0) {const preCur = [...currentPath] // key: 保留之前的状态, 每次获取子元素的子门路后还回去
      currentPath.push(word)
      helper(target.slice(word.length), wordBank, currentPath, path)
      currentPath = preCur
    }
  }
}

说句实话我也不晓得我在写啥

const allConstruct = (target, wordBank) => {if (target === '') return [[]]

  const result = []

  for (const word of wordBank) {if (target.indexOf(word) === 0) {const suffix = target.slice(word.length)
      const suffixWays = allConstruct(suffix, wordBank)
      const targetWays = suffixWays.map(way => [word, ...way])
      result.push(...targetWays)
    }
  }

  return result
}

const allConstruct = (target, wordBank, memo = {}) => {if (target in memo) return memo[target]
  if (target === '') return [[]]

  const result = []

  for (const word of wordBank) {if (target.indexOf(word) === 0) {const suffix = target.slice(word.length)
      const suffixWays = allConstruct(suffix, wordBank, memo)
      const targetWays = suffixWays.map(way => [word, ...way])
      result.push(...targetWays)
    }
  }

  memo[target] = result
  return result
}

勾销递归, 应用数组记录, 钻研每个之前状况对之后状况的影响

const fib = n => {const table = Array(n + 1).fill(0) // 初始化
  table[1] = 1 // 开始, 人工赋值
  for (let i = 0; i < n; i++) {
    // 每个格子会影响前面的两个格子
    table[i + 1] += table[i]
    table[i + 2] += table[i]
  }
  return table[n]
}

console.log(fib(6))
console.log(fib(7))
console.log(fib(8))
console.log(fib(50)) // 很快就出后果了

const gridTraveler = (m, n) => {const table = Array(m + 1)
    .fill() //undefined 不能 map
    .map(() => Array(n + 1).fill(0)) // 间接 full 会指向雷同的援用

  table[1][1] = 1

  for (let i = 0; i <= m; i++) {for (let j = 0; j <= n; j++) {if (i + 1 <= m) table[i + 1][j] += table[i][j] // 二维数组左值边界查看
      if (j + 1 <= n) table[i][j + 1] += table[i][j]
    }
  }
  return table[m][n]
}

console.log(gridTraveler(3, 2))

布局你的 table 记录什么
找出你的 table 的 size , 维度
初始化 table 的值是多少
找到更新 table 的初值种子 (寻找那个和决定 / 随机 / 资源没有关系的状况个别是 0 /1)
迭代更新 table
考查每个格子对将来的格子的影响

target 是 0 的时候, 肯定是 true

const canSum = (targetSum, numbers) => {const table = Array(targetSum + 1).fill(false)
  table[0] = true
  for (let i = 0; i <= targetSum; i++) {if (table[i] === true)
    numbers.forEach(number => {table[number + i] = true
    })
  }
  return table[targetSum]
}

console.log(canSum(7, [3, 2]))
console.log(canSum(7, [4, 2]))
console.log(canSum(7, [5, 6, 2]))
console.log(canSum(300, [7, 14]))

小哥陷入有限循环的问题: 不要时刻判断 length, 这样不好

const howSum = (targetSum, numbers) => {const table = Array(targetSum + 1).fill(null)
  table[0] = []
  for (let i = 0; i <= targetSum; i++) {if (table[i] !== null)
      numbers.forEach(number => {table[number + i] = [...table[i], number]
      })
  }
  return table[targetSum]
}

console.log(howSum(7, [3, 2]))
console.log(howSum(7, [4, 2]))
console.log(howSum(7, [5, 6, 2]))
console.log(howSum(300, [7, 14]))

const bestSum = (targetSum, numbers) => {const table = Array(targetSum + 1).fill(null)
  table[0] = []
  for (let i = 0; i <= targetSum; i++) {if (table[i] !== null)
      numbers.forEach(number => {if (!table[number + i] || table[number + i].length > table[i].length)
          // 如果是 null 须要给予初值
          table[number + i] = [...table[i], number]
      })
  }
  return table[targetSum]
}

console.log(bestSum(7, [3, 2]))
console.log(bestSum(7, [4, 2]))
console.log(bestSum(7, [5, 6, 2]))
console.log(bestSum(300, [7, 14]))

const canConstruct = (target, wordBank) => {const table = Array(target.length + 1).fill(false)
  table[0] = true

  for (let i = 0; i <= target.length; i++) {if (table[i] === true)
      wordBank.forEach(word => {if (target.slice(i, i + word.length) === word)
          table[i + word.length] = true
      })
  }

  return table[target.length]
}

console.log(canConstruct('', ['cat']))
console.log(canConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(canConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))
console.log(canConstruct('CatVsDog', ['Cat', 'V', 's', 'Dog']))
console.log(
  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
    'ef',
    'eeeeeeeeeee'
  ])
)
console.log(
  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
    'e',
    'ee',
    'eee',
    'eeeeeeeeeee'
  ])
)

const countSum = (target, wordBank) => {const table = Array(target.length + 1).fill(0)
  table[0] = 1

  for (let i = 0; i <= target.length; i++) {if (table[i] !== 0)
      wordBank.forEach(word => {if (target.slice(i, i + word.length) === word)
          table[i + word.length] += table[i]
      })
  }

  return table[target.length]
}

console.log(countSum('', ['cat']))
console.log(countSum('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(countSum('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(countSum('CatVsDog', ['Cat', 's', 'Do']))
console.log(countSum('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))
console.log(countSum('CatVsDog', ['Cat', 'V', 's', 'Vs', 'Dog']))

const allConstruct = (target, wordBank) => {const table = Array(target.length + 1)
    .fill()
    .map(() => [])

  table[0] = [[]]
  for (let i = 0; i < target.length; i++) {
    wordBank.forEach(word => {if (target.slice(i, i + word.length) === word) {
        // 对于以后格子的每个状况都须要进行后续单词的查看
        const newCombinations = table[i].map(subArr => [...subArr, word])
        // 减少而不是笼罩
        table[i + word.length].push(...newCombinations)
      }
    })
  }

  return table[target.length]
}

console.log(allConstruct('', ['cat']))
console.log(allConstruct('CatVsDog', ['Cat', 'Vs', 'Dog']))
console.log(allConstruct('CatVsDog', ['at', 'Vs', 'Dog']))
console.log(allConstruct('CatVsDog', ['Cat', 's', 'Do']))
console.log(allConstruct('CatVsDog', ['Cat', 'VsD', 'Vs', 'Dog']))
console.log(allConstruct('CatVsDog', ['Cat', 'V', 's', 'Vs', 'Dog']))

遇见 dp 问题:

留神到重叠的子问题
决定什么是最小的输出
想一下记忆化递归
想一下列表化问题
画一个策略, 树或者数组

Keep curious, keep learning

【Jeff 在写代码】无关代码的所有的所有

记忆化递归

fib

个别实现

优化

旅行者 gridTraveler

递归版

dp 版

这类问题的总结

canSum

递归

dp

howSum

递归版

dp 版

bestSum

tips: 应用递归的思路

递归版

dp 版

这三个问题的总结

canConstruct

递归版

我的实现(谬误版)

视频的实现

我的实现(正确版)

dp 版

我的实现

视频实现

countConstruct

递归版

我的实现

视频实现

dp 版

allConstruct

递归版

我的实现

视频实现

dp 版

列表化 tabulation

fib(nth)

gridTraveler

这类问题的总结

canSum

howSum

bestSum

canConstruct

countConstruct

allConstruct

总结