### 算法设计策略II:动态规划

```Dynamic Programming


DP适用问题第一特征：重叠子问题




DP适用问题第二特征：最优子结构



Fibonacci Number
Binomial Coefficients
Shortest paths in DAGs
Chain matrix multiplication
Longest Increasing Subsequences


DP经典问题





Knapsack 背包问题

Edit Distance
The Partition Problem



Bellman发明的。它作为一种重要的工具在应

DP适用问题的第一特征






Fibonacci Number


f(n) = f(n-1) + f(n-2)
f(0)=0, f(1)=1
n>1
Fibonacci Number


long long fib_r(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return (fib_r(n-1) + fib_r(n-2));
}


Fibonacci Number




Fibonacci Number


long long fib_c(int n)
{
if (f[n] == -1)
f[n] = fib_c(n-1) + fib_c(n-2);
return (f[n]);
}
long long fib_c_driver(int n)
{
f[0] = 0;
f[1] = 1;
for (int i=2; i<=n; i++) f[i] = -1;
return (fib_c(n));
}
Fibonacci Number


long long fib_dp(int n)
{
long long f[MAXN + 1];
f[0] = 0;
f[1] = 1;
for (int i=2; i<=n; i++)
f[i] = f[i-1] + f[i-2];
return (f[n]);
}
Fibonacci Number


long long fib_ultimate(int n)
{
/* back2,back1 are last two values of f[n] */
long long back2 = 0, back1 = 1;
long long next;
if (n==0) return 0;
for (int i=2; i<n; i++) {
next = back1 + back2;
back2 = back1;
back1 = next;
}
return (back1+back2);
}
Binomial Coefficients


C(n,k)表示从n个不同物体中选出k个的组合数
C(n,k)=n!/((n−k)!k!)=C(n-1,k-1)+C(n-1,k)
Pascal’s triangle
Matrix representation
Binomial Coefficients
Const int MAXN = 100;
long long binomial_coefficient(int n, int k)
{
long long bc[MAXN+1][MAXN+1];
for (int i = 0; i<=n; i++) bc[i][0] = 1;
for (int j = 0; j<=n; j++) bc[j][j] = 1;
for (int i = 1; i<=n; i++)
for (int j=1; j<i; j++)
bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
return ( bc[n][k] );
}
Shortest paths in DAGs

dist(D) = min{dist(B)+edge(BD), dist(C)+edge(CD)}
= min{dist(B)+1, dist(C)+3}

Shortest paths in DAGs
Topologically sort vertices in G;
Initialize all dist(.) values to INF
dist(s) = 0
for each v ∈ V , in linearized order do
dist(v) = min(u,v) ∈E { dist(u) + w(u,v) }
Example

6
r

5
s
0
2
t

1
u
7

–1
4
3
2
v

–2
w

Example
6
r

5
s
0
2
t

1
u
7

–1
4
3
2
dist[r] = , dist[s] = 0
v

–2
w

Example
6
r

5
s
0
2
t
2
1
u
7
6
–1
4
3
2
v

–2
w

Example
6
r

5
s
0
2
t
2
1
u
7
6
–1
v
6
–2
4
3
2
dist[t]=min{dist[s]+2, dist[r]+3}
w
4
Example
6
r

5
s
0
2
t
2
1
u
7
6
–1
v
5
–2
4
3
2
dist[u]=min{dist[s]+6, dist[t]+7}
w
4
Example
6
r

5
s
0
2
t
2
1
u
7
6
–1
v
5
–2
4
3
2
dist[v]=min{dist[t]+4, dist[u]-1}
w
3
Example
6
r

5
s
0
2
t
2
1
u
7
6
–1
v
5
–2
w
3
4
3
2
dist[w]=min{dist[t]+2, dist[u]+1, dist[v]-2}



Dist[x]。





Dk(i) = opt { Dk-1(j) + cost(i,j) }



DP适用问题的第二特征



Ak+1×Ak+2×…×Ak的最优解。
Chain matrix multiplication
Chain matrix multiplication
Chain matrix multiplication
For 1≤ i≤k≤j ≤n, define
C(i,j) = minimum cost of multiplying Ai×Ai+1×…×Aj
for i = 1 to n: C(i, i) = 0
for s = 1 to n - 1:
for i = 1 to n - s:
j=i+s
C(i, j) = min{C(i, k) + C(k + 1, j) +mi-1·mk·mj : i≤k ≤j}
return C(1, n)
The subproblems constitute a two-dimensional table, each of
whose entries takes O(n) time to compute. The overall
running time is thus O(n3).
Chain matrix multiplication



Ai×Ai+1×…×Aj的一个最优加全部括号把乘积

Ai×Ai+1×…×Ak和Ak+1×Ak+2×…×Ak的最优



sicily1345 能量项链

。项链是头尾相接的。求释放的能量的总和的

Longest Increasing Subsequences
Longest increasing subsequence

Algorithm:
Longest Increasing Subsequences
L(0) = 1, P(.) = -1
For i = 1, 2, …, n
L(i) = 1 + max0<j<i{L(j)}, where Sj<Si
P(i) = j
L(i) is the length of the longest path ending at i (plus 1).
Time complexity is O(n2), the maximum being when the
input array is sorted in increasing order.
Position i
1
2
3
4
5
6
7
8
Sequence Si
Length Li
Predecessor Pi
5
1
-1
2
1
-1
8
2
1
6
2
1
3
2
2
6
3
5
9
4
6
7
4
6
Longest Increasing Subsequences
Position i
1
2
3
4
5
6
7
8
s[i]
5
2
8
6
3
6
9
7
l[i]
1
1
2
2
2
3
4
4
p[i]
-1
-1
1
1
2
5
6
6



sicily1060 Bridging Signals （需要用特殊法

sicily1685 Missile（最长不单调子序列，数据

sicily1448 Antimonotonicity（最长不单调子序








1.
2.

（状态转移方程）






01背包问题

01背包问题





f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }。











f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }




for i=1..N
for v=V..0
f[v]=max{f[v], f[v-c[i]] + w[i]};




void ZeroOnePack(cost,weight){
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
}

01背包问题的伪代码就可以这样写：
for i=1..N
ZeroOnePack(c[i],w[i]);








sicily1782 Knapsack
sicily1146 采药
sicily1342 开心的金明





f[i][v]=max{ f[i-1][v], f[i][v-c[i]]+w[i] }


O(VN)的算法

for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
void CompletePack(int cost,int weight)
{
for(int v=cost;v<=V;++v)
f[v] >?= f[v-cost]+weight;
}


01背包按照v=V..0的逆序来循环，要保证第i次




（两种背包容量）分别为V和U. 物品的价值w[i].

f[i][v][u]表示前i件物品付出两种代价分别为v和u时

f[i][v][u]=max{ f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i] }




“二维费用”的条件有时是以这样一种隐含的






poj1014 Dividing
sicily1077 Cash Machine(可能不算多重背包，




f[k][v]表示前k组物品花费费用v能取得的最大权值，

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i] | 物品i属于组k}



for 所有的组k
for v=V..0
for 所有的i属于组k
f[v]=max{f[v],f[v-c[i]]+w[i]}

“for v=V..0”这一层循环必须在“for 所有的i属



sicily1750 运动会




f'[0..V-c[i]]。那么这个主件及它的附件集合相当于Vc[i]+1个物品的物品组，其中费用为c[i]+k的物品的



sicily1346 金明的预算方案



Tianyi Cui《背包九讲》，可在课程页面上下

》（俗称“黑书”）1.5节 动态规划



j
a1,a2,…,an，求该序列形如的  a[k ]子段和的
k i




bi = bi-1 + ai
bi-1>0
ai
bi-1<=0
b1 = a1
ans = max{ bi }
ans=b=a[1];
for(i=2;i<=n;i++)
{
if (b>0) b+=a[i]; else b=a[i];
if (b>ans) ans=b;
}



poj1050 To the Max（最大子矩阵和问题）
sicily1091 Maximum Sum（最大m段子段和问

sicily1888 Circular Sequence （求一次最大
MAX，判断是否是整个串，如果是就求一次最






d[i][j] = d[i-1][j] + d[i-1][ j-c[i] ]
d[0][0]=1,d[0][1…s]=0

d[0]=1; d[1…s]=0;
for (i=1; i<=n; i++)
{
for (j=s; j>=c[i]; j--)
{
d[j] += d[j-v[i]];
}
}



d[0]=1;d[1…s]=0;
for (i=1; i<=n; i++) {
for (j=s; j>=c[i]; j--){
for(k=1;k<=m[i];k++){
if (j-k*c[i]>=0)
d[j] += d[j-k*c[i]];
else break;
}
}
}



d[0]=1;d[1…s]=0;
for (i=1; i<=n; i++)
{
for (j=s; j>=c[i]; j--)
{
for(k=1;;k++)
{
if (j-k*c[i]>=0) d[j] += d[j-k*c[i]];
else break;
}
}
}

d[0]=1; d[1…s]=0;
for (i=1; i<=n; i++)
{
for (j=c[i];j<=s; j++)
{
d[j] += d[j-c[i]];
}
}






memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
int dp(int s)
{
if(vis[s]) return d[s];
vis[s] = 1;
int& ans = d[s];
ans = -INF; // INF = 1<<30
for(int i=1;i<=n;i++)
if(s>=v[i]) ans >?= dp(s-v[i]) + 1;
return ans;
}



void print_ans(int *d, int s)
{
for(int i=1; i<=n; i++)
if (s>=v[i] && d[s]==d[s-v[i]]+1)
{
printf(“%d “, i);
print_ans(d, s-v[i]);
break;
}
}



min[0] = max[0] = 0;
for(int i=1; i<=s; i++) {
min[i]=INF; max[i]=-INF;
}
for(int j=1; j<=n; j++)
for(int i=1; i<=s; i++)
if( i>=v[j]) {
min[i] <?= min[i-v[j]] + 1;
max[i] >?= max[i-v[j]] + 1;
}
cout << min[s] << “ “ << max[s] << endl;

sicily 2014 Dairy Queen
sicily1005 Roll Playing Games（此题为搜索

sicily1564 HOUSING（可看成硬币问题）
sicily1902 Counting Problem



2
6
1
1
2
8
4
5
6
8







y个位置到达底层的最小路径得分。

Path(x,y)一定包含子问题D(x+1,y)或D(x+1,y+1)

D(x,y)＝min{D(x+1,y),D(x+1,y+1)}+a(x,y)
D(n,k)＝a(n,k)，k＝1，…，n

D(x,y)表示从第X层第y个位置到达底层的最小


sicily1563 GECKO





t[i,i]=0
t[i,j] = mini<=k<j{t[i,k]+t[k,j]+w(vivkvj)}

sicily 1822 决斗


A[i,j]=1，则i与j决斗时，i总是赢，如果A[i,j]=0，





meet[i,j]记录i和j是否相遇，能为1，否则为0，问题转化为能

meet[i,j]=1，否则meet[i][j]=0。






Party at Hali-Bula


n个人形成一个关系树，每个节点代表一个人，

Party at Hali-Bula


Party at Hali-Bula




i点及其子树的最多人数。
Party at Hali-Bula






dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j是i的儿子)
dp[i][1] = 1 + ∑dp[j][0] (j是i的儿子)

Party at Hali-Bula









(dp[j][0] > dp[j][1] && dup[j][0] == 0) ||
(dp[j][0] < dp[j][1] && dup[j][1] == 0) ||
(dp[j][0] == dp[j][1])，则dup[i][0] = 0

Strategic game




Strategic game



dproot[ i ]表示以i为根的子树，在i上放置一个

all[ i ]表示看守住整个以i为根的子树需要多少

dproot[i] = 1 + ∑all[j] (j是i的儿子)；
all[i] = min( dproot[i], ∑dproot[j](j是i的儿子) )；
Strategic game








x=00101100，即十进制整数44.





TSP问题。
n <= 16 (重要条件,状态压缩的标志)
TSP




5 ＝ 0000000000000101；（2进制表示）

31 ＝ 0000000000011111； （2进制表示）

4；
TSP




TSP


k表示i集合中去掉了j点得到的集合，s是集合k

TSP


min( dp[( 1<<n ) – 1][j] ) ( 0 <= j < n )；


• 判断点j 是否属于集合i ：i & (1<<j)
• 在集合i 中去除点j ：i –(1<<j) 或者i & ( ~( 1 << j ) )
• 在集合i 中加入点j ：i | (1<<j)

• 问题描述：给出一个带权有向图G=(V, E)，

• 如果暴力穷举所有路径，复杂度不低于O(N!)

• 状态表示：用ans[j][i]表示以j点为起点，并且经

• 状态转移：

s 表示i 集合中去掉了j点的集合，k 遍历集合s 中

• 最后结果便是所有ans[j][i]的最大值.



2000）


Moving one of his feet from the central point to any side
points will consume 2 units of his strength. Moving from
one side point to another adjacent side point will
consume 3 units, such as from the top point to the left
point. Moving from one side point to the opposite side
point will consume 4 units, such as from the top point to
the bottom point. Yet, if he stays on the same point and
tread again, he will use 1 unit.



d[i][j][k]为跳到第k个舞步时，左脚在位置i，右脚在位



d[i,j,k]=min{ d[s[k],j,k+1]+cost(i,s[k]),
d[i,s[k],k+1]+cost(j,s[k]) }
d[i,j,n]=min{ cost(i,s[n]), cost(j,s[n]) }

Longest Common Substring
Longest Common Substring


c[i][j]记录序列Xi和Yj的最长公共子序列的长度。


c(i, j) = 0
c(i, j) = c(i-1, j-1) + 1
c(i, j) = max{c(i,j-1), c(i-1,j)}
if i=0 or j=0
if i, j>0 and xi = yj
if i, j>0 and xi ≠ yj
Edit Distance



When a spell checker encounters a possible misspelling, it looks in
its dictionary for other words that are close by. What is the
appropriate notion of closeness in this case?
A natural measure of the distance between two strings is the extent
to which they can be aligned, or matched up. Technically, an
alignment is simply a way of writing the strings one above the other.
For instance, here are two possible alignments of SNOWY and
SUNNY:
S–NOWY
–SNOW–Y
SUNN– Y
SUN– –NY
Cost: 3
Cost: 5
The ' – ' indicates a 'gap'; any number of these can be placed in
either string. The cost of an alignment is the number of columns in
which the letters differ. And the edit distance between two strings is
the cost of their best possible alignment.
Edit Distance


Our goal is to find the edit distance between two strings
x[1…m] and y[1…n]. What is a good subproblem?
How about looking at the edit distance between some
prefix x of the first string, x[1…i], and some prefix of the
second, y[1…j]? Call this subproblem E(i, j). Our goal
objective, then, is to compute E(m, n).
Edit Distance



For this to work, we need to somehow express E(i, j) in
terms of smaller subproblems.
Let's see—
what do we know about the best alignment
between x[1…i] and y[1…j]? Well, its rightmost column
can only be one of three things:
E(i, j) = min{1 + E(i-1, j), 1 + E(i, j-1), diff(i, j) + E(i-1, j-1)}
where diff(i, j) is defined to be 0 if x[i] = y[j] and 1
otherwise.
Edit Distance

For instance, in computing the edit distance between
EXPONENTIAL and POLYNOMIAL, subproblem E(4, 3)
corresponds to the prefixes EXPO and POL. The
rightmost column of their best alignment must be one of
the following:
Thus, E(4, 3) = min{1 + E(3, 3), 1 + E(4, 2), 1 + E(3, 2)}.
Edit Distance

The answers to all the subproblems E(i, j) form a twodimensional table.
Edit Distance

The algorithm for edit distance:

The overall running time is just the size of the table,
O(mn).
























sicily上的一些dp题：
sicily1010 Zipper
sicily1011 Lenny's Lucky Lotto
sicily1019 Apple Tree （树型dp）
sicily1057 Rhyme Schemes
sicily1073 Pearls
sicily1123 The Longest Walk（状态压缩dp）
sicily1148 过河（路径压缩，贪心动态规划）
sicily1158 Pick numbers
sicily1222 单词选择（这题的hash很恶心）
sicily1264 Atomic Car Race （基本dp题）
sicily1404 Hie with the Pie（状态压缩dp）
sicily1687 Permutation
sicily1822 Fight Club
sicily1828 Minimal
```