A programmer who can’t do algorithms is not a good front end

Fundamentals of dynamic programming

This programmer inner monologue: dynamic planning is really not good to get started, because he and the conventional problem solving thinking is not the same. That’s the beauty of dynamic programming, because it gives you a new way to think about problems.

Introduction to persuade you do not go to learn what messy concept, directly on the topic.

Cheat sheet labuladong algorithm portal: labuladong. Making. IO/algo / / by one-third

Basic Exercises (LeetCode)

70, 198, 309, 322

Climb the stairsleetcode70

One step at a time and two steps at a time

dp[i] = dp[i-1]+dp[i-2]

He constructs the array dp[I] as I from 0 to n

Instead of the traditional recursion fn = f(n-1) + f(n-2), which subdivides the problem from the top down and stops at solved problems.

Var climbStairs = function(n) {if(n===0){return 1} if(n===1){return 1} return climbStairs(n-1) + Var climbStairs = function(n) {let hashMap = [1,1] let rec = function (index=n){ if(hashMap[index]){ return hashMap[index] } hashMap[index] = rec(index-1) + rec(index-2) return Var climbStairs = function(n) {let dp = [1,1] for(let I =2; i<=n; i++){ dp[i]= dp[i-1]+dp[i-2] } return dp[n]}; Var climbStairs = function(n) {let temp0 = 1 let temp1 = 1 let temp for(let I =2; i<=n; i++){ temp = temp1 temp1 = temp + temp0 temp0 = temp } return temp1};Copy the code

Al shabaableetcode198

Broken points:

1. Define the status,dp[I] represents the maximum amount stolen from the I house

2. Whether the state transfer steals the I home

At this time, the maximum amount is DP [i-2] + NUMs [I].

If you do not steal the I house, the maximum amount is DP [i-1].

dp[i] = Math.max(dp[i-2]+nums[i] , dp[i-1])

Optimal substructure state transition equation for overlapping subproblems

Robbery ⅱleetcode213

Ideas:

— — > 1. The end does not steal the first | | don’t steal the first

2. Dp [I] (I = 0 to n-2)

3. If you do not steal the money from the first house, the DP will start from the second house to the last house

4. Get the most value

Break point: Don’t think of dynamic programming as a one-step bible. Dynamic programming is just a tool that can only solve a small part of the problem. When you break down complex problems into subdivisions that can be solved with dynamic programming, you are left with work

The best time to buy or sell stocks includes a freeze periodleetcode309

I indicates the number of days. J indicates the current status. Dp [I][j] indicates the current maximum amount

Change changeleetcode322

Dp [I] indicates the minimum number of coins for I yuan

Group photo ~

Ps: This should only be a small part of the dynamic programming, in the short term can help myself to have a superficial feeling of dynamic programming, these exercises after doing the feeling is that I think I understand, do also know, and then to do a new topic, god can still play like this. You probably think you get it, but you probably overfit it. Only by practicing, summarizing and seeing more scenes can we make further progress.

More subdivided knapsack problem in dynamic programming, more complex various scenarios, to the next stage, heh heh