Dynamic programming

  • Dynamic programming is a method of algorithm design.
  • It decomposes a problem into overlapping subproblems and solves the original problem by repeatedly solving the subproblems.

The Fibonacci sequence is a classic dynamic programming problem

One, one, two, three, five, eight, thirteen...Copy the code

The expression, n >= 2, the NTH term is always F(n) = F(n-1) + F(n-2).

  • Defining subproblem

    F(n) = F(n - 1) + F(n - 2)
Copy the code

  • Execute subproblems repeatedly

    Loop from 2 to n, execute the subproblemCopy the code

So let’s do a couple of LeetCode algorithm problems

LeetCode 70. Take the stairs

  1. Title description:

    Suppose you're climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer.Copy the code

  2. Their thinking

  • Climbing to the NTH step can be one step on the n-1 step, or two steps on the n-2 step
  • F(n) = F(n – 1) + F(n – 2)
For example, if n=3, the way to get to level 3 is the way to get to level 2 plus the way to get to level 1, which is 2 + 1Copy the code
  1. Using dynamic programming
  • Solution a:
var climbStairs = function(n) {
   if (n < 2) return 1
   Db [n] = db[n] = db[n]
   let db = [1.1.2] // subscript 2, that is, 2 steps
   for (let i = 2; i <= n; i ++) {
       db[i] = db[i - 1] + db[i - 2]}return db[n] // db --> [1, 1, 2, 3, 5]}; Time complexity: O(n) Space complexity: O(n)Copy the code
  • Solution two advanced version:
var climbStairs = function(n) {
   if (n < 2) return 1
   let dp0 = 1; // The method used to represent the 0th order
   let dp1 = 1; // The method used to represent the first order
   for (let i = 2; i <= n; i ++) {
       const temp = dp0
       dp0 = dp1 // keep dp0 as the penultimate numberDp1 = dp1 + temp dp1 = dp1 + tempreturndp1 }; Time: O(n) Space: O(1)

Copy the code

2.LeetCode 198

  1. Title description:

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night. Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm. Popular point is: can't steal contiguous room continuouslyCopy the code

—

Example 1: Input: [1,2,3,1] Output: 4 Explanation: Steal House 1 (amount = 1), then steal House 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4. Example 2: Input: [2,7,9,3,1] Output: 12 Explanation: Steal House 1 (amount = 2), House 3 (amount = 9), then House 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.Copy the code
  1. Their thinking
-f (k) = Max (F(k) + A(k), F(k-1)) -f (k) = Max (F(k-2) + A(k), F(k-1))Copy the code
Input:1.2.3.1] output:4

1. k = 1, there is only one room, the maximum amount is F(1) = 1
2. k = 2There are two rooms and the maximum amount isMath.max( F(1), F(2))3. k = 3There are three rooms and the maximum amount isMath.max( F(1) + F(3), F(2))4. k = 4, there are four rooms, the maximum amount is the maximum amount of the first two rooms, plus the fourth, compared with the maximum amount of the first three houses, the larger value isMath.max( F(2) + A(4), F(3F(k) = Max (F(k -)2) + A(k), F(k - 1))Copy the code
  • Solution a:
var rob = function(nums) {
   const length = nums.length
   if (length === 0) return 0
   // The subscript of the design dp represents the number of houses
   // The index is 0, that is, the maximum amount of money robbed in the first 0 houses is 0; The index is 1, that is, the maximum amount of money robbed in the previous house is NUMs [0].
   const dp = [0, nums[0]] 
   for (let i = 2; i <= length; i ++) {
   / / child problem of general term formula: F (k) = Max (F (k - 2) + A (k), F (k - 1))
       dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1])}returndp[length] }; Time complexity: O(n) Space complexity: O(n)Copy the code
  • Solution two advanced version:

var rob = function(nums) {
   const length = nums.length
   if (length === 0) return 0
   let dp0 = 0
   let dp1 = nums[0] // The maximum amount of money that can be robbed from the previous house
   for (let i = 2; i <= length; i ++) {
       const dp2 = Math.max( dp0 + nums[i - 1], dp1 )
       dp0 = dp1 
       dp1 = dp2
   }
   returndp1 }; Time: O(n) Space: O(1)
Copy the code

Conclusion:

Dynamic programming is to solve the original problem by repeatedly solving sub-problems, that is, the general formula of F(n), and then deal with some special cases, such as: n = 0, n = 1.Copy the code