“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

Dynamic Programming

Four key points:

  1. Recursion (recursion + memorization ==> recursion, the primary use of the way, skilled can directly use recursion), the lowest level of recursion has the initial value, so from the bottom up the way to push up the results can be obtained, this way is recursion
  2. * State definition: opt[n], dp[n], fib[n]
  3. * the equation of state equation (dp) : opt [n] = bestOf (opt [n – 1) + opt [n – 2),…).
  4. Optimal substructure

Fibonacci series (primary DP)

The recursive formula

F[n] = F[n-1] + F[n-2]
Copy the code

State transition equation

F[0] = 0, F[1] = 1 for (let I = 2; i <= n; i++) { F[i] = F[i-1] + F[i-2] }Copy the code

Maximum increasing subsequence

The recursive formula

dp[i] = Math.max(dp[0], dp[1], ... dp[n-1])
Copy the code

State transition equation

for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j ++) {
        if (nums[j] < nums[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1)
        }
    }
}
Copy the code

COUNT THE PATHS

The recursive formula

opt[i, j] = opt[i-1, j] + opt[i, j-1]
Copy the code

State transition equation

for (let i = 0; i < m; i++) { for (let j = 0; i < n; J++) {if (a = = = [I, j] 'clearing') {opt [I, j] = opt [j] I - 1, + opt [I, j - 1]} else {opt [I, j) = 0}}}Copy the code

DP vs backtracking vs greed

  • Backtracking (recursion) — repeated calculations

    When there is no optimal substructure, backtracking is the optimal solution, exhausting all possibilities

  • Greedy — always locally optimal solution

    You can use it when the local optimal is the global optimal

  • DP — Records local optimal substructures

    When there is double calculation in backtracking, the local optimal value is written down in the form of cache to avoid double calculation. Then through the dynamic transfer equation, to deduce the optimal value of the next state, to achieve the effect of dynamic programming