You see what he wrote what no posteriority what the optimal sub-structure of the big head, I also big head % ...... ......
Dynamic programming generally solves two types of problems, one is the optimization problem, which is to ask you the maximum value of the minimum number of whatever, the other is the total number of programs.
There are many types if you break it down,
I've seen a lot of them (I'm a sophomore, currently preparing for NOIP)
(you have a lot of questions there and I'll just say the names)
Rucksacks, upstairs, even the 9 lectures have been put up I won't go into it ......
The longest non-ascending Non-declining subsequence problems (for example, the flight of the Pampas Eagle Birthday Moot is a classic non-declining deformation)
Resource allocation problems (for example, window arrangement, horse barn problems, machine allocation problems)
Interval kinetic reversion (product maximization, energy necklaces, etc.)
Longest common **** subsequence problems (there's a genetic coding seems to be);
Solution tree's like the stair climbing problem ........................
Dynamic There are many, many types of planning, because he is very flexible, our teacher once found us 100 DP equations, but that is useless, strong memory simply can not remember, the key is to understand.
In-depth a little bit on the optimization of DP, time-space dimensionality reduction (that is, with other methods to do, or for example, the backpack was originally two-dimensional space optimization should become one-dimensional), tree DP (this I will not).
(Optimization inside a very classic question "crossing the river")
I on the DP is the kind of sudden enlightenment ...... don't look at say "dynamic programming" what bluff, in fact, is a comparison of a calculation, know what he What do you do with the question up to have a clue, the equation ah thought ah have ......
Mainly also read more questions, right, from the simple start, to understand his ideas ...... write their own dynamic return to pay attention to the following problems:
1, The premise is to make sure that you are doing is a dynamic return to the question ...... see more will also know what type of questions they are facing
2, the second premise is the idea to be right (I do the question when I first think of the question of the dimensions of time and space, and then think of the equation based on this), the equation is correct,
I really can not think of it can be first look at the problem solution, to understand people's ideas, do not look at the standard program to make the program out of ......
3, pay attention to the array do not open too small, generally are about to open up a little bigger, such as his data range is 1 ~ 100, the array on the opening of the 0 ~ 101. This is to prevent the crossing of boundaries, because a lot of the DP assignment of the initial value of the time will use F[0],F[0,0]
4, the initial value to be correct, because a lot of DP other places are correct because the initial value is assigned wrong and all over the case is very common ...... (such as the currency system inside the USACO)
5, DP loop range to be correct. Generally according to the question to determine the scope of how much to write (such as the window problem, this afternoon to write this question because the cycle is written wrong has been AC can not)
USACO also has a lot of DP questions, you can do ......
All of the above hand-typed, I hope to be able to help you.
I'm also a person who is learning, the above may not be all correct, but it's very useful to me, and it's kind of my experience. I hope that in the future, we can learn together and exchange plus progress together
QQ: 340131980
1. resource problem 1
----- machine allocation problem
F[I,j]:=max(f[i-1,k]+w[i,j-k])
2. resource problem 2
----- -01 Backpack problem
F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]);
3. Linear Dynamic Programming 1
----- Simple longest non-degenerate subsequence
F:=max{f[j]+1}
4. Segmentation Problem 1
---. --- Stone merging
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
5. Profiling Problem 2
----- Polygon profiling
F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a);< /p>
6. profiling problem 3
------ product maximization
f[i,j]:=max(f[k,j-1]*mult[k,i]);
7. resource problem 3
----- System Reliability (Full Backpack)
F[i,j]:=max{f[i-1 ,j-c*k]*P[I,x]}
8. Greedy Dynamic Programming 1
----- Fast Food Problem
F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3}
9. Greedy Dynamic Programming 2
9. p>
----- Crossing the river f=min{{f(i-k)} (not stone)
{f(i-k)}+1} (stone); +Greedy compressed state
10. Dissecting Problems 4
----- Polygonal-Discussed Dynamic Programming
F[i,j]:=max{positive positive f[ I,k]*f[k+1,j];
Negative g[I,k]*f[k+1,j];
Positive and negative g[I,k]*f[k+1,j];
Negative f[I,k]*g[k+1,j];} g is min
11. Tree Dynamic Programming 1
----- additive binary tree ( from sides to root node model)
F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}
12. Tree Dynamic Programming 2
----- Selecting Classes (Multinomial to Binary Tree, Top-Down Model)
F[I,j] denotes maximal credits obtained by selecting j assignments with i as the root node credits
f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c}
13. Counting Problem 1
----- weights weighing
f[f[f[0]+1]=f[j]+k*w[j];
(1<=i<=n; 1&& lt;=j<=f[0]; 1<=k<=a;)
14. Recursion 1
------Nuclear Power Plant Problems
f[-1]:=1; f[0]:=1;
f:=2*f[i-1]-f[i-1-m]
15. Recursion 2< /p>
------ Division of Numbers
f[i,j]:=f[i-j,j]+f[i-1,j-1];
16. Maximum Submatrix 1
----- One Maximum 01 Submatrix
f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1, j-1])+1;
ans:=maxvalue(f);
17. Deterministic Problem 1
Can ----- be divided by 4
g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false;
g[i[i,j],v[i,j-1],v[i-1, j-1],v[i-1, j-1]:=false;
g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j)
18. Deterministic Problem 2
Whether or not ----- is divisible by k
f[I,j±n mod k]:=f[i-1,j]; -k<=j<=k; 1<=i& lt;=n
20. Linear Dynamic Programming 2
----- Square Elimination Game
f[i,i-1,0]:=0
f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k),
f[i,p,k+len[j]]+f [p+1,j-1,0]}
ans:=f[1,m,0]
21. Linear Dynamic Programming 3
----- Longest Common **** Substring, LCS Problem
f[i,j]={0(i=0)&(j=0);
f[i-1,j-1]+1 (i& gt;0,j>0,x=y[j]);
max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]);
22. maximal submatrix2
----- maximal weighted 01 submatrix O(n^2*m)
< p>Start of enumeration, compress into series, find maximal sum of fields, clear in case of 023. resource problem 4
----- Boxing Problem (Deterministic 01 Backpacking)
f[j]:=(f[j] or f[j-v]);
24. numeric triangles 1
----- Plain の Numeric Triangle
f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);
25. Numeric Triangle 2
----- Haruhi Piggy Adventures of Hill
Violent Dynamic Programming on the same stage
if[i,j]. =min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j]
26. Bidirectional Dynamic Programming1
Digital Triangles3
----- Little Fatty Getting a License
f[i,j]:=max(f[i-1,j]+a[i,j] ,f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])
27. digital triangle 4
-----Crossing Pawns
Boundary initialization
f[i,j]:=f[i-1,j]+f[i,j-1];
28. digital triangle 5
-----Plain Bricklaying
f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]);
29. Numeric Triangle 6
-----Optimized Bricklaying
f[I,j,k]:=max{g[i-1,j -k,k-1]+sum[I,k]}
30. linear dynamic planning 3
----- whack-a-mole'
f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j])
31. tree dynamic Planning 3
----- Gluttonous Hydra
32. State Compression Dynamic Planning 1
----- Artillery Position
Max(f[Q*(r+1)+k],g[j]+num[k])
If (map and plan[k]=0) and
(( plan[P] or plan[q]) and plan[k]=0)
33. recursion3
----- love letter scribe
f:=f[i-1]+k*f[i-2]
34. recursion4
----- mismatch
f:=(i -1)(f[i-2]+f[i-1]);
f[n]:=n*f[n-1]+(-1)^(n-2);
35. Recursion 5
----- Number of Maximum Regions of a Straight Line Split Plane
f[n]:=f[n-1]+n
:=n*(n+1) div 2 + 1;
36. recursion 6
----- Maximum number of regions in the folded subplane
f[n]:=(n-1)(2*n-1)+2*n;
37. recursion 7
----- Maximum number of regions in the subplane of a closed curve
f[n]:=f[n-1]+2 *(n-1)
:= sqr(n)-n+2;
38 Recursive world 8
----- Number of ways to divide a triangle by a convex polygon
f[n]:=C(2*n-2,n-1) div n;
For a k-side
f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3)
39 Recursive world 9
-----Catalan series in general form
1,1,2,5,14,42,132
f[n]:=C(2k,k) div (k+1);
40 Recursive world 10
----- Colored Light Arrangement
Circular Coloring Problem in Permutations
f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); (f[1]:=m; f[2]:=m(m-1);
41 Linear Dynamic Programming 4
----- Finding the Number
Linear Scan
sum:=f+g[j];
(if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);)
42 Linear Dynamic Programming 5
----- Invisible Wings
min:= min{abs(w/w[j]-gold)};
if w/w[j]<gold then inc(i) else inc(j);
43 Segmentation Problems 5
----- Maximum Reward
f:=max(f,f[j]+(sum[j]-sum)* i-t
44 Shortest 1
-----Floyd
f[i,j]:=max(f[i,j],f[i,k]+f[k,j]);
ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i, j,k],j]/s[i,j];
45 Dissection Problem 6
----- Little H's Hut
F[l,m,n]:=f[l-x,m-1,n-k]+S(x,k);
46 Counting Problem 2
----- Meteorite's Secret (Counting Problems in Permutations)
Ans[l1,l2,l3,D]:=f[l1+1,l2,l3,D+1]-f[l1+1,l2,l3,D];
F[l1,l2,l3,D]:=Sigma(f[o,p,q,d-1]*f[l1-o,l2-p,l3-q,d]);
47 Linear Dynamic Programming
------ Choral Queueing
Twice F:=max{f[j]+1} + enumerate the central node
48 Resource Problems
------ Ming Ming's Budget Solution: dynamic programming with added flowers
f[i,j]:=max(f[i,j],f[l,j-v-v[fb ]-v[fa]]+v*p+v[fb]*p[fb]+v[fa]*p[fa]);
49 Resource Problems
----- Chemical Yard Crating Clerk
50 Tree Dynamic Programming
----- The Joy of Gathering
f[i,2]:=max(f[i,0],f[i ,1]);
f[i,1]:=sigma(f[t^.son,0]);
f[i,0]:=sigma(f[t^.son,3]);
51 Tree Dynamic Programming
----- Palace Guard
f[i,2]:=max(f[i,0], f[i,1]);
f[i,1]:=sigma(f[t^.son,0]);
f[i,0]:=sigma(f[t^.son,3]);
52 Recursive Heaven and Earth
----- Boxes and Balls
f[i,1]:=1;
f [i,j]:=j*(f[i-1,j-1]+f[i-1,j]);
53 Dual Dynamic Programming
----- Finite Gene Sequence
f:=min{f[j]+1}
g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c ,i,j])
54 Maximum Submatrix Problem
----- inhabited space
f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]),
min(f[i,j,k-1],f[i-1,j-1,k])),
min(min(f[i-1,j,k-1],f[i,j-1,k-1]),
f[i-1,j-1,k-1]))+1;
55 Linear Dynamic Programming
------ Schedule
f:=max{f[j]}+P[I]; (e[j]< ;s)
56 Recursive world
------ Combinatorial numbers
C[I,j]:=C[i-1,j]+C[I-1,j-1]
C[I,0]:=1
57 Tree dynamics planning
----- Directed Tree k Median Problem
F[I,r, k]:=max{max{f[l,I,j]+f[r,I,k-j-1]},f[f[l,r,j]+f[r,r,k-j]+w[I,r]]}
58 Tree Dynamic Programming
-----CTSC 2001 Selection of Courses
F[I,j]:=w(if i∈P)+f[l, k]+f[r,m-k](0≤k≤m)(if l<>0)
59 Linear Dynamic Programming
----- Multiple Histories
f[i,j]:=sigma{f[i-k,j-1]}(if checked)
60 Backpacking Problem (+1 Backpacking Problem + Backtracking )
-----CEOI1998 Substract
f[i,j]:=f[i-1,j-a] or f[i-1,j+a]
61 Linear Dynamic Programming (strings)
-----NOI 2000 Mystery of the Old City
f[i,1,1]:=min {f[i+length(s),2,1], f[i+length(s),1,1]+1}f[i,1,2]:=min{f[i+length(s),1,2]+words[s], f[i+length(s),1,2]+words[s]}
62 Linear dynamic programming
----- minimum number of words
f[i,j]:=max{f[I,j],f[u-1,j-1]+l}
63 Linear Dynamic Programming
-----APIO2007 Data Backup
State compression + pruning off the state j*2 before each stage j and after j*2+200 Greedy Dynamic Programming
f:=min(g[i-2]+s,f[i-1]);
64 Tree Dynamic Programming
-----APIO2007 Wind Chimes
f:=f[l]+f[r]+{1 (if c[l]<c[r])}
g:=1 (d[l]<c[r])}
g:=1 (d[l]< lt;>d[r]) 0(d[l]=d[r])
g[l]=g[r]=1 then Halt;
65 Map dynamic programming
-----NOI 2005 adv19910
F[t,i,j]:=max{f[t-1,i-dx[d[[t]] ],j-dy[d[k]]]+1],f[t-1,i,j];
66 Map Dynamic Programming
----- Optimization for NOI 2005 adv19910
F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j;
67 Goal Dynamic Programming
-----CEOI98 subtra
F[I,j]:=f[I-1,j+a] or f[i-1,j-a]
68 Goal Dynamic Programming
----- Vijos 1037 Build a Twin Tower Problem
F[value, delta]:=g[value+a,delta+a] or g[value,delta-a]
69 Tree Dynamic Programming
----- Cable Networks
f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j])
leaves>=p>=l, 1<=q<=p;
70 Map Dynamic Programming
-----vijos a question
F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]);
71 Maximum Submatrix Problem
----- Maximum Field Sum Problem
f:=max(f[i-1]+b,b); f[1]:=b[1]
72 Maximum Submatrix Problem
----- Maximum Subcube Problem
Enumerate the beginning of a set of edges i, compressed into the matrix B[I,j]+=a[ x,I,j]
Enumerate another set of edges actually, make maximal submatrix
73 Bracket sequences
----- Linear Dynamic Programming
f[I,j]:=min(f[I,j],f[i+1,j-1](ss[j]="() "or("[]")),
f[I+1,j+1]+1 (ss[j]="("or"["] , f[I,j-1]+1 (s[j]=") "or"]" )
74 Checkerboard cut
-----Linear Dynamic Programming
f[k,x1,y1,x2,y2]= min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2],
f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]
min{}}
75 Probabilistic Dynamic Programming
----- Cong and Coco ( NOI2005)
x:=p[p[i,j],j]
f[I,j]:=(f[x,b[j,k]]+f[x,j])/(l[j]+1)+1
f[I,i]=0
f[x,j]=1
76 Probabilistic Dynamic Programming
-----. ---blood relations
F[A, B]=(f[A0, B]+P[A1, B])/2
f[I,i]=1
f[I,j]=0(I,j do not have the same genes)
77 Linear Dynamic Programming
----- duel
F[I,j]=(f[I,j] and f[k,j]) and (e[I,k] or e[j,k]),i<k<j
78 Linear Dynamic Programming
----- Dancer
F[x,y,k]=min(f[a[k],y,k+1]+w[x,a[k]],f[x,a[k],k+1]+w [y,a[k]])
79 Linear Dynamic Programming
----- Block Game
F[I,a,b,k]=max(f[I,a+1,b,k],f[i+1,a+1,a+1,k'],f[I,a+1,a+1,k '])
80 Tree Dynamic Programming (Double Recording)
-----NOI2003 Truant Kids
Plain words enumerate node i and the two farthest nodes j,k O(n^2)
Each node records the two largest values and records from which neighboring node this maximum was passed, respectively. nodes were passed. When traversing to a child node, simply check if the maximum value was passed from that child node. If so, take the next largest, otherwise take the largest value
81 Tree Dynamic Programming (Complete Binary Tree)
-----NOI2006 Network Tolls
F[I,j,k] denotes that among all the users governed by a point i, there are j users as A. On each ancestor u of I, if N[a]>N is labeled 0 otherwise 1, and compressed into k with a Binary state compression into k. Minimum spend in this case
F[I,j,k]:=min{f[l,u,k and (s<<(i-1))]+w1,f[r,j-u,k and (s<<(i-1))]}
82 Tree dynamic programming
---- -IOI2005 River
F:=max
83 Memorized search
-----Vijos some question, forgot
F[pre,h,m]:=sigma{SDP(I,h+1,M+i)} (pre<=i<=M+1)
84 Status Compressed Dynamic Planning
-----APIO 2007 Zoo
f[I,k]:= f[i-1,k and not (1<<4)] + NewAddVal
85 Tree Dynamic Planning
----- Visiting the Art Museum
f[i,j-c×2]:= max ( f[l,k], f[r,j-c×2-k] )
86 String dynamic planning
-----Ural 1002 Phone
if exist(copy(s,j,i-j)) then f:=min(f,f[j]+1);
87 Multiprocess dynamic Planning
-----CEOI 2005 service
Min( f[i,j,k], f[i-1,j,k] + c[t[i-1],t] )
Min( f[i,t[i-1],k], f[i-1,j,k] + c[j,t] )
Min( f[i, j,t[i-1]], f[i-1,j,k] + c[k,t] )
88 Multi-process Dynamic Programming
-----Vijos1143 Triple Fetch Number of Squares
max(f[i,j,k,l],f[i-1,j-R[m,1],k-R[m,2],l-R[m,3]]);
if (j=k) and (k=l) then inc(f[i,j,k,l],a[j,i-j]) else
if (j=k) then inc(f[i,j,k,l],a[j,i-j]+a[l,i-l]) else
if (k=l) then inc(f[ i,j,k,l],a[j,i-j]+a[k,i-k]) else
if (j=l) then inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]) else
inc(f[i,j,k,l],a[j,i-j]+a[k,i-k]+a[l, i-l]);
89 Linear Dynamic Programming
-----IOI 2000 Post Office Problem
f[i,j]:=min(f[I,j],f[k,j-1]+d[k+1,i]);
90 Linear Dynamic Programming
-----Vijos 1198 Best Topic Selection
if j-k>=0 then Min(f[i,j],f[i-1,j-k]+time(i,k));
91 Backpacking Problem
----- USACO Raucous Rockers
Multiple backpacks without duplicating the items but with a restrictions.
F[I,j,k] denotes the decision to the i-th item, the j-th backpack, which costs k space.
f[I,j,k]:=max(f[I-1,j,k],f[I-1,j,k-t]+p,f[i-1,j-1,maxtime-t])
92 Multi-Process Dynamic Programming
----- Touring Canada (IOI95, USACO)
d[i,j]= max{d[k,j]+1(a[k,i] & j<k<i),d[j,k]+1(a[I,j] & (k<j))}.
f[i,j] denotes the number of cities passed from the starting point when one person reaches i and the other person reaches j. d[i,j]=d[j,i] so we restrict i>j
Analyze the state (i,j), which may be obtained by k arriving at i in (k,j)(j<k<i) (way 1), or it may be (j,k) (k<j) in which k exceeds j to reach i to get (way 2). But it can't be (i,k)(k<j) in which k reaches j to get it, because then a duplicate path may occur. Even if there will be no duplicate paths, then it is obtained by (j,k) by way 2 as well, so no solution is missed Time complexity O(n3)
93 Dynamic programming
-----ZOJ cheese
f[i,j]:=f[i-kk*zl[u,1],j-kk*zl[u,2]]+a[i -kk*zl[u,1],j-kk*zl[u,2]]
94 Dynamic Programming
-----NOI 2004 berry Linear
F[I,1]:=s
F[I,j]:=max{min{s-s[l-1]},f[l-1,j-1]} (2≤j≤k , j≤l≤i)
95 Dynamic Programming
-----NOI 2004 berry Totally Undirected Graph
F[I,j]:=f[i-1,j] or (j≥w) and (f[i-1,j-w])
96 Dynamic Programming
-----Stone Merging Quadrilateral Inequality Optimization
m[i,j]=max{m[i+1,j], m[i,j-1]}+t[i,j]
97 Dynamic Planning
-----CEOI 2005 service
(k≥long, i≥1) g[i, j, k]=max{g[i-1,j,k- long]+1, g[i-1,j,k]}
(k<long, i≥1) g[i, j, k]=max{g[i-1,j-1,t-long]+1, g[i-1,j,k]}
(0 ≤ j ≤ m, 0 ≤ k<t) g[0,j,k]=0;
ans. = g[n,m,0].
State optimization: g[i, j]=min{g[i-1,j], g[i-1,j-1]+long}
Where (a, b)+long=(a', b') is computed as:
When b+long ≤ t: a '=a; b'=b+long;
When b+long ＞t: a'=a+1; b'=long;
Boundary conditions for planning:
When 0≤i≤n, g[i,0 ]=(0,0)
98 Dynamic Planning
-----AHOI 2006 Treasure Trove Passage
f[k]:=max{f[k-1]+x[k,j]-x[k,i-1], x[k,j]-x[k,i-1]}
99 Dynamic Planning
----- Travel
A) The least expensive travel plan.
Let f denote the minimum cost of one day's stay in the i-th hostel from the starting point; and g denote the minimum number of days required to meet the minimum cost of one day's stay in the i-th hostel from the starting point. Then:
f=f[x]+v, g=g[x]+1
x satisfies:
1, x<i, and d - d[x] <= 800 (the maximum number of trips in a day).
2. For all t < i, d - d[t] <= 800, it must satisfy:
A. g[x] < g[t] (when f[x] = f[t]) B. f[x] < f[t] (all other cases)
f[0] = 0, g[0] = 0. Ans:= f[n + 1], g[n+1].
B). The travel plan with the least number of days.
The method is actually very similar to the first question.
Let g' denote the minimum number of days from the starting point to the i-th hostel for one day's stay; and f' denote the minimum cost required from the starting point to the i-th hostel for one day's stay, provided the minimum number of days is satisfied. Then:
g' = g'[x] + 1, f' = f'[x] + v
x satisfies:
1, x<i, and d - d[x] <= 800 (the maximum distance traveled in a day).
2. For all t < i, d - d[t] <= 800 must satisfy:
f'[x] < f'[t] g'[x] = g '[t] when
g'[x] < g'[t] other cases
f'[0] = 0, g'[0] = 0. Ans:=f '[n + 1], g'[n+1].
100 Dynamic Planning
-----NOI 2007 cash
y:=f[j]/(a[j]*c[j]+b[j]);
g:=c[j]*y*a+y*b;
f:=max(f,g)