Brush these 15 DP questions, can only chance the topic into dachang

preface

Some guy’s dynamic programming, and I, as a guy who’s committed to being the best algorithm writer in the culinary world, have to brush part of the problem, so I found a little bit, and now we’re going to talk about, like me, what I found.

Drainage of the

Brush these 20 dichotomy questions, may still tear the big factory interview

Brush these a few pile of questions, or may not tear the big factory interview

Brush these 30 tree questions, may still tear the big factory interview

Brush these 20 linked list questions, may still tear the big factory interview

The body of the

Summary of this week’s learning now, MY skull pain panic, what things can not think of, but in order not to break their own weekly summary of the next goal, can only water a few words;

Dp seems to be a bottleneck for all beginners. Anyway, when it comes to the difficulty of algorithms, the first thing that comes to mind is DP. To brag about how difficult it is for others in the interview, you would say that you could throw a few DP at random to make it difficult for the interviewee’s elder brother emerges in endless stream.

Actually learning algorithm to the interview of the algorithm, when you use dp no, tree, list these are super hot topic to the fire, so the dp algorithm for the purpose of learning for the front-end to interview, belongs to a kind of accumulation, is a classic topic learning, met with the original one, pass directly, difficulties is the feeling of the college entrance examination last two mathematics questions, So what? So go over the best ones and… I only have one dish of chicken, I don’t know, anyway, I will continue to make it in the future, and I will learn more dp. After all, this thing is really interesting. If you are interested, you can come here to learn da Shen’s summary

Above, really can not blow down, offline, sleep; We’ll do the bits next week; Come on!

Topic summary

Buy and sell stocks

121. The best time to buy and sell stocks
122. The best time to Buy and sell stocks II
123. The best time to Buy and sell stocks III
188. The best time to buy and sell stocks IV
309. The best time to buy or sell stocks includes the freeze period
714. The best time to buy or sell stocks includes fees

Al shabaab

198. Robbery
213. Robbery II
337. House robbery III

Memorization recursion

118. Yang Hui Triangle
70. Climb the stairs
Interview question 08.06. Hannotta question

other

322. Change
518. Change II — Make up the plan
5. The longest subroutine string

The title

121. The best time to buy and sell stocks

Analysis of the

Buy and sell 1 time, do not need interval, do not charge poundage
Dp_0 represents the maximum profit in the non-holding state, and dp_1 represents the minimum cost in the holding state

2.5. As there is only one transaction, dp_1 should be as large as possible to ensure the minimum purchase cost, while DP_0 should also be kept as high as possible to ensure the maximum sale 3. Max (dp_0,dp_1+nums[I]), dp_1 = math. Max (dp_1,-nums[I]) 4. Base case dp_0 =0 dp_1 = -nums[I]

var maxProfit = function(prices) {

    let dp_0 = 0,dp_1 = prices[0]
    for(let i = 0; i<prices.length; i++){ dp_0 =Math.max(dp_0,dp_1+prices[i])
        dp_1 = Math.max(dp_1,-prices[i]) // Because you can only buy and sell once, here
    }
    return dp_0
}
Copy the code

122. The best time to Buy and sell stocks II

Analysis of the

Buy and sell n times, do not need interval, do not charge poundage
Dp [I][j] represents the maximum profit on the I +1 day (I is the substandard value, and the corresponding days should be +1). When the state is J, I is [0,len-1], j 0 means no holding, and 1 means holding
Equation of state: dp [I] [0] = math.h Max (dp [1] [I – 1] + temp, dp [I – 1] [0]), dp [I] [1] = math.h Max (dp [1], [I – 1] dp [0] – [I – 1] temp)
base case: dp[0][0] = 0, dp[0][1] = -temp
Time complexity O(n){O(n)}O(n), space complexity O(n){O(n)}O(n)

var maxProfit = function(prices) {
    const dp = new Array(prices).map(() = > [])
    dp[0] [0] = 0,dp[0] [1] =prices[0]
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1] [1]+prices[i], dp[i-1] [0])
        dp[i][1] =Math.max( dp[i-1] [1], dp[i-1] [0]-prices[i])
    }
    return dp[prices.length-1] [0]};Copy the code

Analyze – Compress spatial variables

To compress this, convert the two-dimensional array into two variables dp_0,dp_1
Time complexity O(n){O(n)}O(n), space complexity O(1){O(1)}O(1)


var maxProfit = function(prices) {
    let dp_0 = 0,dp_1 = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        const temp_0 = dp_0
        dp_0 = Math.max(dp_0,dp_1+prices[i])
        dp_1 = Math.max(temp_0-prices[i],dp_1)
    }
    return dp_0
}
Copy the code

123. The best time to Buy and sell stocks III

Analysis of the

Buy and sell 2 times, do not need interval, do not charge poundage
Dp [I][j][k] represents the maximum profit on the day I +1 (I is the substandard value, and the corresponding number of days is +1), when the holding status is J and the trading times is K, where I is [0,len-1], j is 0, indicating no holding, and 1 indicates holding
Buying is recorded as a single transaction, selling is not recorded as a single transaction
State transition equation: dp[i][0][k] = Math.max(dp[i-1][0][k],dp[i-1][1][k]+prices[i]), dp[i][1][k] = Math.max(dp[i-1][1][k],dp[i-1][0][k-1]-prices[i])
Base case 1 — all the states when the number of transactions is 0, if this is holding 1, that is, and the number of transactions is 0 conflict, as long as the number of transactions did not rise, any transaction is a rogue, so it is equivalent to no transaction 0; If it doesn’t hold a zero, then it’s initialized to zero;
Base case 2 — Since the state with the number of transactions 0 has been processed, the number of transactions is at least 1, that is, holding is normal operation, not holding is abnormal, give a 0 to occupy the position;
The most difficult part here is to determine the base case. In short, if the number of transactions and the holding status are abnormal, the transaction will fail. Only when the number of transactions is used and the holding status is updated synchronously, can it be considered as a normal transaction.

var maxProfit = function (prices) {
    const dp = Array.from(prices).map(() = > Array.from({length:2}).map(() = > new Array(3)))
    const len = prices.length

    for(let i = 0; i<len; i++){for(let k = 1; k<=2; k++){// base case 1 -- when k is 0
            dp[i][0] [0]  = 0
            dp[i][1] [0] = 0 // As long as the number of trades does not increase, any trade is a hooligan
            if(i === 0) {// Base case 2 -- The status of the first day
                dp[0] [0][k]  = 0 // 
                dp[0] [1][k] = -prices[0]
                continue
            }
            dp[i][0][k] = Math.max(dp[i-1] [0][k],dp[i-1] [1][k]+prices[i])
            dp[i][1][k] = Math.max(dp[i-1] [1][k],dp[i-1] [0][k-1]-prices[i])
        }
    }
    return dp[len-1] [0] [2]}Copy the code

188. The best time to buy and sell stocks IV

The same operations and analysis as 123. Best time to Buy and sell stocks III
Prices. length is in the range of [0,1000]. Prices. length in III is in the range [1,pow(10,5)], so it can be used directly

var maxProfit = function(k, prices) {
    const len = prices.length
    if(len<2) return 0
    // dp[I][j][k] -- I = [0,len-1] j:0,1; K to [0, k]
    const dp =Array.from(prices).map(() = > Array.from({length:2}).map(() = > new Array(k+1).fill(0)))
    for (let i = 0; i < prices.length; i++) {
        // Base case1 -- when the number of transactions is 0
        dp[i][0] [0] = 0
        dp[i][1] [0] = 0
        for (let j = 1; j <= k; j++) {
            if(i === 0) {// Base Case2 -- first day trading
                dp[0] [0][j] = 0
                dp[0] [1][j] = -prices[0]
                continue
            }
            dp[i][0][j] = Math.max(dp[i-1] [0][j],dp[i-1] [1][j]+prices[i])          
            dp[i][1][j] = Math.max(dp[i-1] [1][j],dp[i-1] [0][j-1]-prices[i])          
        }
    }
    return dp[prices.length-1] [0][k]
};

Copy the code

309. The best time to buy or sell stocks includes the freeze period

Analysis of the

Buy and sell n times, need interval 1 day, do not collect poundage
Dp_0_0 indicates no holding and is not in the cooling period. Dp_0_1 indicates no holding and is in the cooling period. Dp_1_0 in normal condition, there is no cooling period when holding and DP_1_1 is in a contradictory state and is ignored
State transition equation:
- dp_0_0 = Math.max(dp_0_0, dp_0_1);
- dp_0_1 = dp_1_0 + prices[i];
- dp_1_0 = Math.max(dp_1_0,temp – prices[i]);
base case: dp_0_0 = 0, dp_0_1 = 0, dp_1_0 = -prices[0];
Dp_0_0 = 0, dp_0_1, dp_1_0; dp_0_0 = 0, dp_0_1, dp_1_0; So you can directly compress the space complexity to O(1){O(1)}O(1)

var maxProfit = function (prices) {
  const len = prices.length;
  if (len < 2) return 0;
  let dp_0_0 = 0,
    dp_0_1 = 0,
    dp_1_0 = -prices[0];

  for (let i = 1; i < len; i++) {
    const temp = dp_0_0;
    // There is no holding state in cooling, which indicates that there is no holding state in cooling
    dp_0_0 = Math.max(dp_0_0, dp_0_1);
    dp_0_1 = dp_1_0 + prices[i];
    dp_1_0 = Math.max(dp_1_0,temp - prices[i]);
  }
  return Math.max(dp_0_0, dp_0_1);
};

console.log(maxProfit([1.2.4]));

Copy the code

714. The best time to buy or sell stocks includes fees

Analysis of the

Buy and sell n times, no interval, charge handling fee
As a result of want to receive poundage, so not how business is good, must calculate cost go up, before it is without this for example, need to buy low only sell tall become, must consider the possibility that may meet deficit now
The overall analysis is the same as 122. Best Time to Buy or sell stocks II, except that at the time of selling, add fee

 var maxProfit = function(prices, fee) {
    let dp_0 = 0, dp_1 = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        const temp =dp_0
        dp_0 = Math.max(dp_0,dp_1 + prices[i] - fee)
        dp_1 = Math.max(dp_1,temp - prices[i])
    }
    return dp_0
};
Copy the code

198. Robbery

Analysis of the

Dp [I][0] represents the maximum amount of money that was not stolen at the ith house and DP [I][1] represents the maximum amount of money that was stolen
The equation of state: dp [I] [0] = math.h Max (dp [1], [I – 1] dp [I – 1] [0]) dp [I] [1] = dp [0] + [I – 1] nums [I]
base case dp[0][0] = 0 dp[0][1]= numns[0]
Time complexity O(n){O(n)}O(n), space complexity O(n){O(n)}O(n)

var rob = function (nums) {
  const len = nums.length;
  const dp = new Array(len).fill(null).map(() = > new Array(2));
  dp[0] [0] = 0;
  dp[0] [1] = nums[0];
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1] [1], dp[i - 1] [0]);
    dp[i][1] = dp[i - 1] [0] + nums[i];
  }

  return Math.max(dp[len - 1] [0], dp[len - 1] [1]);
};
Copy the code

Analysis of the

Dimension reduction, each time the value is only related to the previous one, and there are only two state values, so you can directly use two variables dp_0,dp_1
Time complexity O(n){O(n)}O(n), space complexity O(n){O(n)}O(n)

var rob = function (nums) {
    let dp_0 = 0,dp_1 = nums[0]
  for (let i = 1; i < len; i++) {
        const temp = dp_0 // save the previous dp_0
        dp_0 = Math.max(dp_0,dp_1)
        dp_1 = temp+nums[i]
    }
    return Math.max(dp_0,dp_1)
}
Copy the code

213. Robbery II

Analysis of the

Dp [I][j][k] where I represents the ith value, j represents whether the first house is stolen, and K represents whether the current house is stolen
State transition equation: DP [I][J][K] = DP [i-1][J][K]
base case: dp[0][0][0] = 0, dp[0][1][1] = nums[0],dp[0][0][1] = -1,dp[0][1][0] = -1
Time (n){O(n)}O(n) Space (n){O(n)}O(n)

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

Copy the code

Analysis of the

Dimensionality reduction, each time the value is only related to the previous one, and the two status values only have two items respectively, so four variables dp_0_0,dp_1_1,dp_1_0,dp_0_1 can be directly used to maintain the state in the iteration process
Time complexity O(n){O(n)}O(n), space complexity O(n){O(n)}O(n)

var rob = function (nums) {
  let dp_0_0 = 0, dp_1_1 = nums[0], dp_1_0 = -1,dp_0_1 = -1  
  for (let i = 1; i < nums.length; i++) {
    const temp_0_0 =  dp_0_0
    const temp_1_0 =  dp_1_0
    dp_0_0 = Math.max(dp_0_0,dp_0_1)
    dp_0_1 = temp_0_0 + nums[i]
    dp_1_0 = Math.max(dp_1_0,dp_1_1)
    dp_1_1 = i === nums.length - 1 ?  dp_1_1 : temp_1_0+nums[i]

  }
  return Math.max(dp_0_0,dp_1_1,dp_1_0,dp_0_1);
};

Copy the code

337. House robbery III

Analysis of the

Each node returns two status values [dp_0,dp_1], where dp_0 indicates that the value of the retaining wall root.val is not taken, and dp_1 indicates that the current maximum value of val is taken
At the beginning, I also tried to use the top-down keep-state method, but it was not appropriate to obtain the maximum state value of a single path. In addition, repeated state nodes were needed to be found
Bottom-up take will ensure that all nodes in the middle of the state of all, the final summary to the root node, to get the maximum, and top-down, finally is distributed, the maximum where not sure, there is also no general dp with an array of all the status value, so in order to an aggregate value, also should consider is from the bottom up, Find the state value of the root node
Time complexity O(n){O(n)}O(n), space complexity O(1){O(1)}O(1)

var rob = function (root) {
  const recursion = (root) = > {
    if(! root)return [0.0];
    const [ldp_0, ldp_1] = recursion(root.left);
    const [rdp_0, rdp_1] = recursion(root.right);

    const dp_0 = Math.max(
      ldp_0 + rdp_0,
      ldp_0 + rdp_1,
      ldp_1 + rdp_0,
      ldp_1 + rdp_1
    );
    const dp_1 = ldp_0 + rdp_0 + root.val;
    return [dp_0, dp_1];
  };
  const [dp_0, dp_1] = recursion(root);
  return Math.max(dp_0, dp_1);
};

Copy the code

118. Yang Hui Triangle

Analysis of the

In Yang Hui’s triangle, both sides are 1
Triangle in the value of num [row] [col] = num [row 1] [col – 1) + num [row 1] [col]
Num [row][col]

var generate = function(numRows) {
    const dp = new Array(numRows)
    for (let i = 0; i < numRows; i++) {
        dp[i] = new Array() ;
        for(let j = 0; j<=i; j++){// Both sides of Yang Hui's triangle are 1
            if(j ===  0  || j === i) {
                dp[i][j] = 1
                continue
            }
            dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
        }      
    }
    return dp
};

console.log(generate(1))
console.log(generate(2))
console.log(generate(5))
Copy the code

70. Climb the stairs

Parse-memorizing recursion – caching corresponding values from the top down

Use map to store keys of different staircase lengths and corresponding path values in the recursive process
Each recursion checks to see if the map already has an answer, and continues recursively if it doesn’t
Base case, [0->1,1->1], uses map to cache values, which can reduce repeated intermediate operations and reduce time complexity
Time complexity O(n){O(n)}O(n), space complexity O(n){O(n)}O(n)

var climbStairs = function(n) {
    const map = new Map()
    map.set(1.1)
    map.set(0.1)
    const recursion= (n) = > {
        if(map.has(n)) return map.get(n)
        const sum =  recursion(n-1)+recursion(n-2)
        map.set(n,sum)
        return sum
    }
    return recursion(n)
};
Copy the code

@analysis — dp

Use dp[I] to indicate how many ways there are when the staircase is I
State transition equation: dp[I] = DP [i-1]+ DP [i-2]
Base case: dp[0] + dp[1] = 1
Time complexity O(n){O(n)}O(n), space complexity O(n){O(n)}O(n)

var climbStairs = function(n) {
    const dp = []
    dp[1] = 1
    dp[0] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1]+dp[i-2]}return dp[n]
}
Copy the code

Interview question 08.06. Hannotta question

Analysis of the

This is a typical recursive problem, starting n values at a time from first, through second, and finally to end
If n === 1, start first -> end
If there is n > 1, then we need to store n-1 values from first -> end -> second and the remaining one directly from first -> end
After step 3, first is currently empty,second has n-1 values, and end has 1 maximum value. This is now equivalent to taking n-1 values from second -> first -> end, and finally finding a full array of N values in end
Time complexity O(n2){O(n^2)}O(n2)

var hanota = function(A, B, C) {
    const len = A.length;
    const recursion = (n,first,second,end) = > {
        if(n === 1) {
            const a = first.pop()
            end.push(a)
            return
        }
        // Move n-1 values from first -> end -> second, then move the last value from first to end
        recursion(n-1,first,end,second)
        end.push(first.pop())
        // Now end has a value, second has n-1 values, and first is null
        Second -> first -> end
        recursion(n-1,second,first,end)
    }
    recursion(len,A,B,C)
};
Copy the code

322. Change

Analysis – The number of coins is infinite

State definition: DP [I] represents the minimum number of coins required to make a total amount of I
Dp [I] = math.min (DP [i-coins[x]])+1
base case: dp[0] = 0
Time complexity O(n∗m){O(n*m)}O(n∗m) where N is the number of coins, m is the total amount of money, and the space complexity is O(m){O(m)}O(m).

var coinChange = function (coins, amount) {
  const dp = new Array(amount + 1)
  // base case
  dp[0] = 0; // If the total amount is 0, no need to fetch
  for (let i = 1; i <= amount; i++) {
    dp[i] = Infinity / / initialization
    for (coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1); }}}return dp[amount] === Infinity ? -1 : dp[amount];
};

// The permutations and combinations are ok, because it is an extreme value
var coinChange = function (coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  // base case
  dp[0] = 0; // If the total amount is 0, no need to fetch
  for (coin of coins) {
    for (let i = 1; i <= amount; i++) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1); }}}return dp[amount] === Infinity ? -1 : dp[amount];
};

Copy the code

518. Change II — Make up the plan

Analysis of the

I never understood why I had to write the outer loop of coins and the inner loop of amount, because 322. Change exchange is a bit similar, both are to raise money, one is to raise the minimum number, and HERE I gather the plan
And because I have the number of options, 1-2-1 is the same thing as 1-1-2, so I just want combinations, I don’t want permutations;
Therefore, if the outer layer is “amount”, it takes into account the order in which coins are taken, and the resulting number is the same, which is not consistent with this case. Therefore, the design of coins is only related to the type of coins, not the order in which coins are taken. Add coins to the above question.
State definition: dp[I] represents the number of options available when the sum is I – given the amount coin array, the number of options varies depending on the coin type
State transition equation: dp[I] = sum(dp[i-coin]) — calculate the number of schemes that can be made when removing a coin
Base case: dp[0] = 1
Time complexity O(n∗m){O(n*m)}O(n∗m) where N is the number of coins, m is the total amount of money, and the space complexity is O(m){O(m)}O(m).

var change = function (amount, coins) {
  const dp = new Array(amount + 1).fill(0); // There are no more options
  dp[0] = 1; // Not fetching is another option

    // In the backpack problem, what are the items in the backpack? For each item, the solution can be updated
  for (coin of coins) {
    for (let i = coin; i <= amount; i++) {
        // Only those higher than the current value need to be updateddp[i] = dp[i] + dp[i - coin]; }}return dp[amount];
};

Copy the code

5. The longest subroutine string

Analysis of the

State definition — dp[I][j] indicates that the substring at [I,j] is a loop substring
State transition equation: DP [I][J] = S [I] === S [J] && DP [I +1][J-1]
Base case: j- I <1 &&s [I] === s[j], dp[I][j] = true, they are the loop string
Dp is a value with no follow-up inferred from the known value, so when dp[I][j] is required, either DP [I +1][J-1] is already known, or it is a base case
So the outer layer is an end value, and then I expands forward in the inner layer

 var longestPalindrome = function(s) {
    const dp =Array.from(s).map(() = > new Array()) 
    let ret = ' '
    for(let j = 0; j <s.length; j++){for(leti =j; i>=0; i--){if( j-i<2 && s[i] === s[j]){
                // base case: single character
                dp[i][j] = true
            }else if(s[i] === s[j] && dp[i+1][j-1]){
                dp[i][j] = true
            }
            if(dp[i][j] && j-i+1>ret.length){
                ret = s.slice(i,j+1)}}}return ret
};


Copy the code

Brush these 15 DP questions, can only chance the topic into dachang

preface

The body of the

Topic summary

Buy and sell stocks

Al shabaab

Memorization recursion

other

The title

121. The best time to buy and sell stocks

122. The best time to Buy and sell stocks II

123. The best time to Buy and sell stocks III

188. The best time to buy and sell stocks IV

309. The best time to buy or sell stocks includes the freeze period

714. The best time to buy or sell stocks includes fees

198. Robbery

213. Robbery II

337. House robbery III

118. Yang Hui Triangle

70. Climb the stairs

Interview question 08.06. Hannotta question

322. Change

518. Change II — Make up the plan

5. The longest subroutine string

Related Posts

Ant Design Vue changes the a-upload-dragger upload status

Write a WebGL composite scenario example with WebSocket

Practical Guide – Quickly build documentation sites