9.1.1 问题描述与状态定义

• 9-1 数字三角形

基础的动态规划

9.1.2 记忆化搜索与递推

• 递归计算

c#include 
    
     #include 
     
      using namespace std;int a[1000][1000];int n;int dp(int i, int j){    return a[i][j] + (i == n ? 0 :max(dp(i+1, j), dp(i+1, j+1)));}int main(){    while(~scanf("%d", &n))    {        for(int i = 1; i <= n; i++)            for(int j = 1; j <= i; j++)                scanf("%d", &a[i][j]);        printf("%d\n", dp(1, 1));    }    return 0;}
     
    

• 递推

c#include 
    
     #include 
     
      using namespace std;int a[1000][1000];int n;int dp(int i, int j){    return a[i][j] + (i == n ? 0 :max(dp(i+1, j), dp(i+1, j+1)));}int main(){    while(~scanf("%d", &n))    {        for(int i = 1; i <= n; i++)            for(int j = 1; j <= i; j++)                scanf("%d", &a[i][j]);        printf("%d\n", dp(1, 1));    }    return 0;}
     
    

• 记忆化搜索

将递归过程中的数保存下来

cint d[1000][1000];int dp(int i, int j){    if(d[i][j] > 0) return d[i][j];    return d[i][j] = a[i][j] + (i == n ? 0 : max(dp(i+1, j), dp(i+1, j+1)));}

9.2.1 DAG模型

DAG(无回路有向图).

二元关系可以使用图来建模

• 9.2 嵌套矩形

矩形的嵌套可以看做一个二元关系,矩形X可以嵌套在Y里,则X->Y就有一条有向边.此外,X不能嵌套自己,也不能被比其小的矩形嵌套,所以这是一个DAG.

• 9.3 硬币问题

9.2.2 最长路及其字典序

1. 建图
2. 记忆化搜索

cint dp(int i){    int &ans = d[i];    if(ans > 0) return ans;    ans = 1;    for(int j = 1; j <= n; j++)        if(G[i][j]) ans = ans > dp(j)+1 ? ans : dp(j)+1;}

1. 递归输出.

cvoid print_ans(int i){    printf("%d ", i);    for(int j = 1; j <= n; j++) if(G[i][j] && d[i] == d[j]+1)    {        print_ans(j);        break;    }}

9.2.3 固定终点的最长路和最短路

• 记忆化搜索

cint dp(int S){    if(vis[S]) return d[S];    vis[S] = 1;    int &ans = d[S];    ans = -1 << 30;    for(int j = 1; j <= n; j++) if(S >= V[j])        ans = max(ans, dp(S-V[j]) + 1);    return ans;}

• 递推

c void cal(int S){    const int INF = 0x3f3f3f3f;    Min[0] = Max[0] = 0;    for(int i = 1; i <= S; i++)    {        Min[i] = INF;        Max[i] = -INF;    }    for(int i = 1; i <= S; i++)        for(int j = 1; j <= n; j++)            if(i >= V[j])            {                Min[i] = min(Min[i], Min[i-V[i]]);                Max[i] = min(Max[i], Max[i-V[i]]);            }}

输出

cvoid 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;        }}