Learning notes

www.bilibili.com/video/BV1Y6…

Memorization recursion

fib

General implementation

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)) / / stuck
Copy the code

Such recursion is evaluated once at a time, resulting in multiple calls

To optimize the

Let’s think about how do we optimize this process

Consider a simplified version of the model, where we observe a function that looks like this

When we recurse twice

So our fib time before is zero

This is too bad

Traversal with memory is DP

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

// Change 1 To set the memo and initial values
const fib = (n, memo = {}) = > {
  // Modify 2 to check whether there is memory
  if (n in memo) return memo[n]
  if (n === 1 || n === 2) return 1
  // Modify 3 recursively with our reference
  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)) // The result will come out soon
Copy the code

Travelers gridTraveler

Let’s start with the minimalist form

This is actually a boundary case

Simple case

With each step, the problem will simplify

So one way to think about it is this

The representational understanding is that

The recursive version

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))
Copy the code

The dp version

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))
Copy the code

A summary of these kinds of questions

Minimum outcome of success and minimum outcome of failure

canSum

Reverse thinking: sum to constant value -> Use constant value to traverse the number group down to 0

recursive

My solution

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]))
Copy the code

Video solution

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
}
Copy the code

The video solution has fewer recursions

dp

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]))
Copy the code

howSum

The recursive version

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]))

Copy the code

The dp version

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 // Unreachable also needs to be logged
  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]))
Copy the code

bestSum

Tips: Use a recursive approach

1. Think about exits, boundary conditions, failure and success conditions
2. Call a recursive function assuming that the recursive function gets the result you want

The recursive version

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])) / /,4,1 [2]
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]))
Copy the code

The dp version

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])) / /,4,1 [2]
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]
Copy the code

Summary of these three questions

canConstruct

Obviously, this is the same kind of problem as canSum

Look for the boundary condition of this problem, the recursive termination condition, and keep decreasing the length of the character until it is empty, failing which is that the remaining character’s children are not in wordBank

1. How do I store matched characters? How to determine if the current character is no longer matched?

The recursive version

My implementation (wrong version)

After each successful match, the string is split, and the results of the operation are queried in turn. When the string is empty, it is a successful result. After the cycle is finished, there is no condition

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']))
Copy the code

If you think about it, there is a big problem with this. The program returns the first split point without checking whether the second split point still meets the condition

console.log(canConstruct('CatVsDog'['Cat'.'VsD'.'Vs'.'Dog']))// Should be true, print false
Copy the code

That’s why the changes were made

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']))
Copy the code

So that solves that problem, but there’s a downside to that, you can’t just stop, you can stop when you find out that the pre is true, so we can use some instead, some will stop the loop when it returns true, Similarly every will break out of the loop when it returns false.

You could also use throw+trycatch to complete the termination loop, but that would be weird and anti-pattern, but I implemented it anyway

Some/every optimization

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']))
Copy the code

Try-catch version

It’s disgusting to watch

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)
    // Return true (string)
    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']))
Copy the code

Implementation of video

We can check from left to right for substrings, which saves a lot of work, and we don’t have to check both sides when we recurse

This is an idea of transformation

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']))
Copy the code

I forgot the use case of the stress test, so I don’t have to think about it

console.log(
  canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef'['e'.'ee'.'eee'.'eeee']))Copy the code

My implementation (correct version)

Well, when we went through the stress test case, we found that using split would split every e, so we would get [“, “], so it would be wrong

So you need to implement a function that only splits once

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

// split a function only once
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']))Copy the code

The dp version

The realization of the I

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)]
}
Copy the code

Video to realize

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]
}

Copy the code

countConstruct

The recursive version

The realization of the I

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
}
Copy the code

Video to realize

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
}
Copy the code

The dp version

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]
}
Copy the code

I think I’m getting pretty good at it

allConstruct

The recursive version

The realization of the I

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: saves the previous state and returns it each time the child path is retrieved
      currentPath.push(word)
      helper(target.slice(word.length), wordBank, currentPath, path)
      currentPath = preCur
    }
  }
}
Copy the code

To be honest, I don’t know what I’m writing

Video to realize

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
}
Copy the code

The dp version

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] = resultreturn result
}
Copy the code

List the tabulation

Eliminate recursion, use array records, and study the effect of each previous situation on the subsequent situation

fib(nth)

const fib = n= > {
  const table = Array(n + 1).fill(0) / / initialization
  table[1] = 1 // Start with manual assignment
  for (let i = 0; i < n; i++) {
    // Each grid affects the next two
    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)) // The result will come out soon
Copy the code

gridTraveler

const gridTraveler = (m, n) = > {
  const table = Array(m + 1)
    .fill() / / undefined cannot map
    .map(() = > Array(n + 1).fill(0)) // Direct full will point to the same reference

  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] // Check the lvalue boundary of a two-dimensional array
      if (j + 1 <= n) table[i][j + 1] += table[i][j]
    }
  }
  return table[m][n]
}

console.log(gridTraveler(3.2))
Copy the code

A summary of these kinds of questions

1. What do you plan your table to record
2. Find the size and dimension of your table
3. What is the value of the initialization table
4. Find the initial seed of the update table (find the seed that has nothing to do with decision/random/resource is usually 0/1)
5. Update table iteratively
6. Examine the effect of each cell on future cells

canSum

When target is 0, it must be 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]))
Copy the code

Little brother into infinite loop problem: do not always judge length, this is not good

howSum

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]))
Copy the code

bestSum

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)// If it is null, the initial value should be given
          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]))
Copy the code

canConstruct

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']))Copy the code

countConstruct

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']))
Copy the code

allConstruct

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) {
        // For each case of the current grid, a subsequent word check is required
        const newCombinations = table[i].map(subArr= > [...subArr, word])
        // Add instead of overwritetable[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']))
Copy the code

conclusion

Encountered dp problems:

1. Notice the overlap subproblem
2. Decide what is the minimum input
3. Think about mnemonic recursion
4. Think about tabulating
5. Draw a policy, a tree or an array

Keep curious, keep learning

[Jeff is writing code] Everything about code