刘怡峰-动态规划.ppt

动态规划
给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条
路,使得所经过的权值之和最小或
者最大.
我们写出状态转移方程:f(i, j)=a[i, j] + min{f(i-1, j)+f(i-1, j + 1)}
如果用递归:
f1:=f(i-1,j+1); f2:=f(i-1,j);
if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
opt[i, j] - 每产生一个f(i, j),将f(i, j)的值放入opt中,以后再次调用到f(i, j)的时候,直接从opt[i, j]来取就可以了。
1017. The Staircases
One curious child has a set of N little bricks (5 ≤ N ≤ 500). From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:

Your task is to write a program that reads from input file one number N and writes to output file the only number Q — amount of different staircases that can be built from exactly N bricks.
Input
Number N
Output
Number Q
Sample
Input output
212 995645335
现在,让我们的来考虑将 n 分成不相等的正整数之和的分划。例如,数 8 的分划如下:
8
7 + 1
6 + 2
5 + 3
5 + 2 + 1
4 + 3 + 1
用 q(n) 来记 n 的分划的个数,这样就有 q(8) = 6。
为了求解 q(n),我们引入一个中间函数 q(k, n),表示数 n 的最小被加数不小于 k 的分划的个数。对于给定的 k 值,q(k, n) 正好分为以下两类:
最小被加数等于 k q(k + 1, n-k) 
最小被加数大于