@ the Author: Runsen

The essence of programming comes from algorithm, and the essence of algorithm comes from mathematics, programming is just to code mathematical problems. —- Runsen

I saw Vivo, Alibaba’s school enrollment algorithm, can clearly know that there is absolutely dynamic planning. If not, then the interviewer is really incompetent. Dynamic programming has fallen N times, and Runsen has been working hard on dynamic programming recently. The article wasted three days.

See Leetcode public articles: mp.weixin.qq.com/s/rhyUb7d8I…

Geek time super brother dynamic programming, pull education algorithm column. Runsen really doesn’t want to die in dynamic programming over and over again. Died a hundred times, learned a hundred times, just couldn’t fucking write it.

Dynamic programming needs to deal with three series: three backpacks, the change problem and the stock problem. Today, Runsen begins to eliminate the most important backpack problem.

Three backpack problems: 01 backpack, multiple backpack, full backpack.

Pre-knowledge of dynamic programming

Noun for dynamic programming

State transition equation: for example, Runsen usually see the state transition equation: dp[n] = DP [n-1] + dp[n-2].

Optimal substructure: generally, a state transfer equation F (n) is derived from the optimal substructure, and the recursive implementation method of the problem can be written quickly. Turn a big problem into a few small problems, and find the best solution in several small problems.

Overlap subproblem: for example, f(5) in the Fibonacci sequence, evaluates f(4) and f(3), resulting in f(4) evaluating f(3) again for Runsen. Basically, a binary tree is pruned by memos stored in memory.

Bottom up: Solve in reverse

Dynamic programming idea

Dynamic programming is a method to find the optimal solution of a problem. General idea: the solution of the problem is transformed into a subproblem ==> solution, ==> recursion, ==> the smallest problem is the initial state that can be obtained directly.

The detailed steps are shown below:

  • Determine if recursive solutions are available, and proceed to Step 2 if so
  • Analyze whether there are a lot of repeating subproblems in the process of recursion
  • Use memos to save solutions to subproblems to avoid heavy double-counting (pruning)
  • Use a bottom-up approach to recursion, called dynamic programming

The key is to find the transition equation.

Fibonacci numbers and stair climbing problems

The Fibonacci sequence first evolved from the rabbit problem,

Suppose a pair of rabbits are born one month to mature, a pair of mature rabbits give birth to one rabbit per month and do not die in one year. So, how many pairs of rabbits can you breed after a year from a newborn pair?

Let’s go straight to the picture below

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…

It turns out that the number of rabbits in each month is equal to the number of rabbits in the previous month + the number of rabbits born in that month is equal to the number of rabbits in the previous month + the number of rabbits in the previous month

The sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

This sequence is known as the Fibonacci sequence. Any number in the Fibonacci sequence is called a Fibonacci number

The Fibonacci sequence, which is usually used to explain recursive functions, tries to solve it recursively, but the time complexity is O(2n)O(2^n)O(2n).

def fib(n) :
  if n <= 1:
      return 1
  return fib(n-1) + fib(n-2)

for i in range(20) :print(fib(i), end=' ')
Copy the code

However, we find that the time complexity is as high as O(2n)O(2^n)O(2n), and the main reason is the existence of repeated calculation. So fib of 3 is going to compute fib of 2 plus fib of 1, and fib of 2 is going to compute fib of 1 plus fib of 0.

This fib of 1 is a completely repeated computation, and instead of recursively calling it again, it should be memorized after the first attempt to dissolve it.

That’s the memo solution, the idea of trading space for time. Put the deliverables in the dictionary Map or list list and fetch them next time instead of double-checking.

The code of memo solution is basically the same as that of dynamic programming.

Fibonacci numbers have a similar problem in Leetcode, this is Leetcode 70. Take the stairs. You can take one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Input: 2 Output: 2 Explanation: There are two ways to climb to the top of the building. 1. 1 + 1 + 2. 2Copy the code

The state transition equation for both the Fibonacci sequence and the stair climbing problem is: DP [I] = DP [i-1] + DP [i-2]. Otherwise, the list Assignment index out of range error will be returned.

The following is the Fibonacci number problem climb the stairs to solve the code, is also Leetcode70 solve the code.

class Solution:
    def Fibonacci(self, n) :
        if n == 0:
            return 1
        if n == 1:
            return 1
        if n > 1:
            dp = [0] * (n+1)
            dp[0] = 1 
            dp[1] =1
            for i in range(2,n+1):
                dp[i] = dp[i-1] +dp[i-2]
            return dp[n]
Copy the code

Leetcode53 maximum suborder sum

The sum of the largest suborders, which Runsen remembers well, is problem 53 in Leetcode.

Input: [...2.1, -3.4, -1.2.1, -5.4], output:6Continuous subarrays [4, -1.2.1] and maximum, for6.Copy the code

Declare two variables, currentSum: the sum of the previous consecutive values, and maxSum: the sum of the current largest subsequence. Maximum suborder and State transition equation F (I) = Max (f(I), f(I)+ NUMs [I +1])

def maxSubArray(nums) :
    Args: nums: integer array Returns: Returns the largest suborder and "" of the integer array
    # compare the current sum of suborders, maximum sum of suborders, return maximum value

    # define the current summation and the largest summation as the first element
    cursum = maxsum = nums[0]
    for i in range(1.len(nums)):
        cursum = max(nums[i], cursum + nums[i])
        print(cursum)
        # compare the current value with the defined maximum suborder and value, and assign the maximum reset value to max_sum
        maxsum = max(cursum, maxsum)
        print(maxsum)
    return maxsum

print(maxSubArray([-2.1, -3.4, -1.2.1, -5.4]))
Copy the code

The front is just the warm-up of dynamic programming, Runsen first into the three knapsacks problem strengthening series, 01 knapsacks problem is the entry stage of dynamic programming.

01 Backpack Problem

The corresponding title: www.acwing.com/problem/con…

The backpack problem is that you only have one item.

Input format: In the first line, two integers, N and V, separated by Spaces, represent the number of items and the volume of the backpack respectively. Then there are N rows, each with two integers vi,wi, separated by Spaces, representing the volume and value of the ith item. Output format: Output an integer, indicating the maximum value. Data range: 0<N,V≤1000; 0 < vi, wi 1000 or lessCopy the code

Enter the sample

4, 5, 1, 2, 4, 3, 4, 4, 6Copy the code

Example output:

8 # 4 + 4 2 + 6Copy the code

Before we solve these problems, how to define dp and how to do the transition equation is important, and it takes about half a minute to do it. I can’t do anything for maybe half an hour.

Many people, like Runsen, define states as two-dimensional arrays: dp[I][v]dp[I][v]dp[I][v] is the maximum value of the first three “items” that happen to be VVV in volume.

The state transition equation is also solved by the way: Dp [I] [j] = Max (dp [j], [I – 1] dp [I – 1] [j – weight [I]] + value [I]) dp [I] [j] = Max (dp [j], [I – 1] dp [I – 1] [j – weight [I]] + Value [I]) dp [I] [j] = Max (dp [j], [I – 1] dp [I – 1] [j – weight [I]] + value [I])

Dp [I][j] = DP [i-1][j]; dp[I] = DP [i-1][j];

Dp [i-1][J-weight [I]] + value[I] dp[i-1][j-weight [I]] + value[I] Dp [i-1][j]] + value[I]

"' @ Author: Runsen @ WeChat: RunsenLiu @ WeChat public number: the king of the Python @ CSDN: https://blog.csdn.net/weixin_44510615 @ making: https://github.com/MaoliRUNsen @ Date: 2020/9/10 "'
# n is the number and v is volume # 4, 5
n, v = map(int.input().split())
goods = []
for i in range(n):
    goods.append([int(i) for i in input().split()])

Initialize, set all values to 0, so that at least the volume is 0 or no item is selected
# Since the for loop iterates through the number first, write the volume inside
dp = [[0 for i in range(v+1)] for j in range(n+1)]
print(goods) # [[1, 2], [2, 3], [3, 4], [4, 5]
I can ignore the # 0
for i in range(1, n+1) :for j in range(1,v+1) :# Determine whether the backpack capacity is greater than the volume of the i-th item
        if j>=goods[i-1] [0] :# Select the maximum between the selected and unselected cases
            dp[i][j] = max(dp[i-1][j], dp[i - 1][j - goods[i - 1] [0]] + goods[i - 1] [1])
        else:
            The ith item is not selected
            dp[i][j] = dp[i-1][j]  
print(dp)
print(dp[-1] [-1])

# Test data
5 10
1 2
2 3
3 4
4 5
5 6
[[1.2], [2.3], [3.4], [4.5], [5.6]]
[[0.0.0.0.0.0.0.0.0.0.0], [0.2.2.2.2.2.2.2.2.2.2], [0.2.3.5.5.5.5.5.5.5.5], [0.2.3.5.6.7.9.9.9.9.9], [0.2.3.5.6.7.9.10.11.12.14], [0.2.3.5.6.7.9.10.11.12.14]]
14  # 2 + 3 + 4 + 5
Copy the code

The code above, if you know how dp is defined and what the state transition equation is, is just as fast as Runsen, which was pretty slow at the time, maybe even better than Runsen.

The above code is a two-dimensional array of state definitions, some guys can even define a one-dimensional array of state definitions, so that space is saved. Runsen couldn’t figure it out. Let’s just say Runsen is a real dish. Diligence can compensate for procrastination!

The one-dimensional array removes state III and JJJ traverses to C [I] in reverse order.

Therefore, Runsens can optimize the solution space and compress the two-dimensional array into a one-dimensional array. At this point, the transfer equation becomes:


d p ( j ) = m a x ( d p ( j ) . d p ( i – w i ) + v i ) dp(j) = max(dp(j),dp(i – wi) + vi) 

"' @ Author: Runsen @ WeChat: RunsenLiu @ WeChat public number: the king of the Python @ CSDN: https://blog.csdn.net/weixin_44510615 @ making: https://github.com/MaoliRUNsen @ Date: 2020/9/10 "'
n, v = map(int.input().split())
goods = []
for i in range(n):
    goods.append([int(i) for i in input().split()])
print(goods) # [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]
dp = [0 for i in range(v + 1)]
for i in range(n):
    # Since we want to place items, we will traverse from space V to 0
    for j in range(v, -1, -1) :# Determine whether the backpack capacity is greater than the volume of the i-th item
        if j >= goods[i][0] :# Update j's state, that is, after the current capacity is put into the item
            dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1])
print(dp)
print(dp[-1])

5 10
1 2
2 3
3 4
4 5
5 6
[[1.2], [2.3], [3.4], [4.5], [5.6]]
[0.2.3.5.6.7.9.10.11.12.14]
14
Copy the code

The above is the final solution of 01 knapsack, due to the limited article, multiple knapsack, complete knapsack will be written in the blog after!!

Unconsciously write a few days now, code repeatedly write, write blog, really tired! Who calls own algorithm is weaker!

Hope to encounter 01 knapsack problem in the future, is in the terrible algorithm interview met Runsen’s love!

If you want to build a relationship with a blogger, you can follow the blogger, or follow the blogger public account “King of Python”, to learn how a non-undergraduate programmer grows up. Blogger ID: Runsen (Weixin_44510615), hope you like, comment, favorites

GitHub, portal ~, GitHub, portal ~, GitHub, Portal ~