Dynamic programming problem

The general pattern of dynamic programming design method

1、 To divide into stages
2、 Determine States and state variables
3、 Determine the decision and write the state transition equation
4、 Looking for boundary conditions
5、 Design and implement the program

Dynamic programming is often used to solve

For example, there are three ways to ask questions ：
1. For maximum / minimum value
2. Is it feasible to ask
3. Find the total number of solutions

If a problem is to get all the solutions and results , Then it's definitely not using dynamic programming

Dynamic programming is similar to divide and conquer , It's all about breaking big problems into small ones , By finding the recurrence relationship between large problems and small problems , Solve small problems , Finally achieve the effect of solving the original problem . But the difference is , The divide and conquer method has been repeatedly calculated many times on subproblems and subproblems , Dynamic programming has memory , Write down the answers to all the sub questions that have been solved by filling out the form , The subproblems needed in the new problem can be extracted directly , Avoid double counting , Thus saving time , So after the problem satisfies the optimality principle , The core of solving problems with dynamic programming is to fill in forms , The form is completed , The optimal solution is found .

for example ： Longest ascending subsequence

f[i][j] It means that the i Number , The last number in the subsequence is j The longest ascending sequence length of , consider f(i) Is it better than f(i-1) Big

1、 Stage ：i
2、 state ：j
3、 Decision making ： To choose or not to choose
4、 Strategy ： ascendant
5、 State transition equation

for example ：listX = [1,5,3,4,8]

step1、 Design status
Remember f(x) For listX The length of the longest subsequence at the end , The longest subsequence length is max(f(x)).
Such as ：
f(1) = 1
f(2) = 2
f(3) = 2
f(4) = 3
f(5) = 4
step2、 How to deduce f(x)
Consider every ratio x Small p, If x>p, that f(x) = f§ + 1, Find the biggest one （ for example 8, Than 1、5、3、4 All big , Can't compare 1 individual , Compare everything ,）
f(1) = 1
f(2) = 2 = max(f(1)+1,f(2)=1)
f(3) = 2 = max(f(1)+1, f(3)>f(2) No comparison ,f(3)=1)
f(4) = 3 = max(f(1)+1, f(2) No comparison ,f(3)+1, f(4)=1)
f(5) = 4 = max(f(1)+1, f(2)+1,f(3)+1,f(4)+1)
step3、 State transition equation
f(x)=max(f§)+1; Conditions ：p<x And listX[p]<listX(x).
From all ratios f(x) Small f( p) Deduce , Then choose the largest

Optimal substructure ：
Big problems can be deduced from small problems , The solution ideas of big problems and small problems are the same .
The local optimal solution of the subproblem will form the global optimal solution of the whole problem .
No aftereffect principle ：
once f(n) determine , Then we can call its value directly , Don't care how it came about .
Such as ： seek f(5) When , I just go straight f(1)、f(2)、f(3)、f(4) Value , Don't calculate how it came , It's been calculated before .

Dynamic programming design method

Forward thrust ： From the beginning , Through the choice of decision-making in the intermediate stage , Reach the end state . Also known as recursion .
Push backward ： Start from the end state , Through the decision-making in the intermediate stage , Reach the start state . Also known as memory search .

Two 、 Longest ascending subsequence

nums = [1,5,3,4,8]
dp = [1]*len(nums)
for i in range(len(nums)):
    for j in range(i):
        if nums[i] > nums[j]:
            dp[i] = max(dp[j]+1,dp[i])
print(max(dp))

3、 ... and 、0-1 knapsack problem

Problem description ：
Yes n Items , They have their own weight and value , There are backpacks of given capacity , How to maximize the total value of the items in your backpack ？
i 1 2 3 4
w 2 3 4 5
v 3 4 5 6
The process
step1、 Abstract the knapsack problem
Xi take 0 or 1, It means the first one i Select or deselect items
Vi It means the first one i The value of an item ,
Wi It means the first one i The volume of items （ weight ）;

step2、 Build a model , The o max(V1X1+V2X2+…+VnXn);
step3、 constraint condition ,W1X1+W2X2+…+WnXn<capacity;
step4、 Definition V(i,j)： Current Backpack Capacity j, front i The value of the best combination of items ;
step5、 Looking for a recurrence relation , There are two possibilities in the face of current goods ：
First of all , The capacity of the bag is smaller than that of the commodity , Can't fit , The value at this time is the same as before i-1 The value of each is the same , namely V(i,j)=V(i-1,j);
second , There is enough capacity to hold the commodity , But it may not reach the current optimal value , So choose the best one between loading and not loading , namely V(i,j)=max｛ V(i-1,j),V(i-1,j-w(i))+v(i) ｝
among V(i-1,j) Means not to pretend ,V(i-1,j-w(i))+v(i) It means that the... Is installed i A commodity , Less Backpack Capacity w(i) But the value increases v(i);
So we can get the recurrence relation ：

1. j<w(i) V(i,j)=V(i-1,j)
2. j>=w(i) V(i,j)=max｛ V(i-1,j),V(i-1,j-w(i))+v(i) ｝

def bag(number, capacity,w, v):
    dp = [[0 for _ in range(capacity+1)] for _ in range(number+1)]
    for i in range(1,number+1): #  Traverse every item 
        for j in range(1,capacity+1): #  Traverse the capacity of the package 
            if j < w[i]:#  It means it can't fit 
                dp[i][j] = dp[i-1][j] #  Equal to the previous item 
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) # dp[i-1][j-w[i]] Before i-1 The best solution of items 
    return dp[-1][-1]
number = 4
capacity = 8
w=[0,2,3,4,5] #  If not from 0 Start , In the cycle ,i and j Need 
v=[0,3,4,5,6]
res = bag(number, capacity,w, v)
print(res)