数字三角形：
1、递归计算
int solve(int i,int j) {
return a[i][j] +(i==n?:max(solve(i+,j),solve(i+,j+)));
}
2、记忆化搜索，不用指明计算顺序，并且保证每个状态只计算一次
int solve(int i,int j) {
if(d[i][j]>=) return d[i][j];
return d[i][j] = a[i][j] +(i==n?:max(solve(i+,j),solve(i+,j+)));
}
3、递推计算
for(int j=;j<=n;j++)
d[n][j] = a[n][j]; for(int i=n-;i>=;i--) {
for(int j=;j<=i;j++) {
d[i][j] = a[i][j] + max(d[i+][j],d[i+][j+]);
}
}
刘汝佳紫书P262
嵌套矩形问题：
典型的二元关系，用图来建模，要是x可以嵌套在y里面，就x->y连线，这个图是有向无环图，有向可以理解，无环的意思就是说，一个矩形不可能直接或者间接的把自己嵌套起来。
问题： 求最多嵌套多少？
就是在这个图上求一个最长路
同数字三角形那样，d(i)表示从节点I出发的最长路的长度
那么d(i) = max{(d[j]+1)|(i,j)ŒE};最后遍历一遍d(i);
#include <bits/stdc++.h>
using namespace std;
#define maxn 10000 int G[maxn][maxn];
int dp[maxn];
int n; //n个节点 //DAG
int DAG(int i) { int &ans = dp[i];
if(ans>)
return ans;
ans = ;
for(int j=;j<=n;j++) {
if(G[i][j])
ans = max(ans,DAG(j)+);
}
return ans;
} void print_ans(int i) { printf("%d ",i);
for(int i=;i<=n;i++) {
if(G[i][j]&&d[i]==d[j]+) {
print_ans(j);
break;
}
}
} int main()
{ memset(dp,,sizeof(dp));
//建图 for(int i=;i<=n;i++)
DAG(i); int ans = -;
int f = -;
for(int i=;i<=n;i++)
{
if(ans<dp[i]) {
ans = dp[i];
f = i;
}
}
print_ans(i); return ;
}
硬币问题：(固定了终点，状态起点是S，状态终点是0)
最长路，最短路。
代码编译不能过，很多函数写同名了，主要记录思想。
以 i 出发的最长路：d(i) = max(d(j)+1|(i,j)<E)
以 i 结束的最长路：d(i) = max(d(j)+1|(j,i)<E)
推荐方案二。
对于方案一，代码细节难度有一点高。
第一： S = 0，本身是可以的，所以dp[N]初始化-1；然后遇到没有计算的，ans = 0;是错误的，原因：节点S不一定到达0状态，但是返回值却是0,而0却可以是别的含义，就是S = 0，不用拿硬币。所以ans = -INF;
用vis数组会方便很多，思路清晰，保证每个状态只访问一次。而且不用担心特殊值之间的冲突了。
然后，求最大，最小两个值，记忆化搜索要写两个。
这时可以递推。注意递推顺序。得到minv,maxv数组，这是可以像记忆化搜索那样搜索路径。
minv[S] ==minv[S-v[j]] + ;
printf("%d ",j);
但是有更好的方案：
就是找到局部最优方案时记录路径。
min_coin[i] = j;
max_coin[i] = j;
然后递归打印，这样就不用循环遍历了
void print_ans(int *min_coin,int S) {
while(S) {
printf("%d ",min_coin[S]);
S-=v[min_coin[S]];
}
}
下面是全部代码：
//固定终点的最长路和最短路 #include <bits/stdc++.h> using namespace std; #define N 10000
#define INF 0x3f3f3f3f const int v[] = {,,,,,,,};
int n; //硬币总数
int S; //总钱数 int dp[N];
bool vis[N]; int dp(int S) { int & ans = dp[S];
if(ans!=-) return ans; ans = -(<<);
for(int i=;i<=n;i++) {
if(S>=v[i])
ans = max(ans,dp(S-v[i])+);
}
return ans;
} //dp方案二,利用vis数组标记状态
int dp(int S) { if(vis[S]) return dp[S];
vis[S] = ; int & ans = dp[S];
ans = -(<<);
for(int i=;i<=n;i++) { if(S>=v[i])
ans = max(ans,dp(S-v[i])+);
}
} void print_ans(int *d,int S) { for(int i=;i<=n;i++) { if(S>=v[i]&&d[S]==d[S-v[i]]+) {
printf("%d ",i);
print_ans(d,S-v[i]);
break;
} } } //改进的print_ans()
void print_ans(int &min_coin,int S) { while(S) {
printf("%d ",min_coin[S]);
S-=v[min_coin[S]];
} } int main()
{
scanf("%d",&S);
memset(vis,,sizeof(vis));
memset(dp,-,sizeof(dp)); int ans = dp(S);
if(ans!=(<<))
printf("OK"); int minv[N] = {};
int maxv[N] = {}; minv[] = maxv[] = ;
for(int i= ;i<=S;i++) {
minv[i] = INF;
maxv[i] = -INF;
} for(int i=;i<=S;i++) {
for(int j=;j<=n;j++) {
if(i>=v[j]) {
minv[i] = min(minv[i],minv[i-v[j]]+);
maxv[i] = max(maxv[i],maxv[i-v[j]]+);
}
}
} printf("%d %d\n",minv[S],maxv[S]); print_ans(minv,S);
print_ans(maxv,S); //空间换时间 int min_coin[N];
int max_coin[N]; for(int i=;i<=S;i++) {
for(int j=;j<=n;j++) { if(i>=v[j]) {
if(minv[i]>minv[i-v[j]]+) {
minv[i] = minv[i-v[j]]+;
min_coin[i] = j;
}
if(maxv[i]<maxv[i-v[j]]+) {
maxv[i] = maxv[i-v[j]] + ;
max_coin[i] = j;
} } } } return ;
}