# topcoder算法教程翻译系列之动态规划

jopen 5年前

DP是一种算法设计技术，它是基于一个递推式和一些初始状态的。子问题的最优解是取决于子子问题的最优解的，并且子子问题的最优解是在求解子问题的最优解之前就已经算好的。

DP的时间复杂度是多项式的，这就使得它比回溯和暴力解法等算法要快得多。

Set Min[i] equal to Infinity for all of i

Min[0]=0

For i = 1 to S

For j = 0 to N - 1

If (Vj<=i AND Min[i-Vj]+1<Min[i])

Then Min[i]=Min[i-Vj]+1

Output Min[S]

 Sum Min. nr. of coins Coin value added to a smaller sum to obtain this sum (it is displayed in brackets) 0 0 - 1 1 1 (0) 2 2 1 (1) 3 1 3 (0) 4 2 1 (3) 5 1 5 (0) 6 2 3 (3) 7 3 1 (6) 8 2 3 (5) 9 3 1 (8) 10 2 5 (5) 11 3 1 (10)

 I The length of the longest non-decreasing sequence of first i numbers The last sequence i from which we "arrived" to this one 1 1 1 (first number itself) 2 1 2 (second number itself) 3 2 2 4 3 3 5 3 3 6 4 5

·        ZigZag -2003 TCCC Semifinals 3

·        BadNeighbors -2004 TCCC Round 4

·        FlowerGarden -2004 TCCC Round 1

S[i][j] = A[i][j] + max(S[i-1][j], S[i][j-1])，上式中i代表行，j代表列，左上角的坐标为{0, 0}。A[i][j]表示在格子(i, j)里的苹果数。注意，当格子处于第一行或是第一列的时候，上面的递推式不一定成立，因为i-1或者j-1会为负数，为了处理这种边界情况，可以先对它们进行初始化。

For i = 0 to N - 1
For j = 0 to M - 1
S[i][j] = A[i][j] +
max(S[i][j-1], if j>0 ; S[i-1][j], if i>0 ; 0)

Output S[n-1][m-1]

·        AvoidRoads -2003 TCO Semifinals 4

·        ChessMetric -2003 TCCC Round 4

Set states(i,j) as unvisited for all (i,j)
Set Min[i][j] to Infinity for all (i,j)

Min[0][M]=0

While(TRUE)

Among all unvisited states(i,j) find the one for which Min[i][j]
is the smallest. Let this state found be (k,l).

If there wasn't found any state (k,l) for which Min[k][l] is
less than Infinity - exit While loop.

Mark state(k,l) as visited

For All Neighbors p of Vertex k.
If (l-S[p]>=0 AND
Min[p][l-S[p]]>Min[k][l]+Dist[k][p])
Then Min[p][l-S[p]]=Min[k][l]+Dist[k][p]
i.e.
If for state(i,j) there are enough money left for
going to vertex p (l-S[p] represents the money that
will remain after passing to vertex p), and the
shortest path found for state(p,l-S[p]) is bigger
than [the shortest path found for
state(k,l)] + [distance from vertex k to vertex p)],
then set the shortest path for state(i,j) to be equal
to this sum.
End For

End While

Find the smallest number among Min[N-1][j] (for all j, 0<=j<=M);
if there are more than one such states, then take the one with greater
j. If there are no states(N-1,j) with value less than Infinity - then
such a path doesn't exist.

·        Jewelry -2003 TCO Online Round 4

·        StripePainter -SRM 150 Div 1

·        QuickSums -SRM 197 Div 2

·        ShortPalindromes -SRM 165 Div 2