数学三角形模型

dp思考方式

从集合角度来考虑DP问题（闫式思考法）

动态规划

• 状态表示(f[i,j])
  • 集合：所有从(1, 1)走到(i, j)的路线
  • 属性：Max/Min/数量
• 状态计算——集合的划分（最后一步是从上面下来|最后一步是从左边过来）

！！！划分依据：“最后一步” 集合划分原则：1、不重复（某情况下） 2、不漏

(1, 1)→(i-1, j)→(i, j) f[i, j] = f[i-1, j] + w[i, j]

(1, 1)→(i, j-1)→(i, j) f[i, j] = f[i, j-1]+ w[i, j]

摘花生原题链接

1015. 摘花生 - AcWing题库

摘花生代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;

int n, m;
int w[N][N];
int f[N][N];
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n,&m);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                scanf("%d",&w[i][j]);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
        printf("%d\n",f[n][m]);
    }
    return 0;
}

最低通行费原题链接

1018. 最低通行费 - AcWing题库

摘花生代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110, INF=1e9;

int n;
int w[N][N];
int f[N][N];

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&w[i][j]);
            
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==1&&j==1)
                f[i][j]=w[i][j];
            else
            {
                f[i][j]=INF;
                if(i>1) f[i][j] = min(f[i][j], f[i-1][j]+w[i][j]);
                if(j>1) f[i][j] = min(f[i][j], f[i][j-1]+w[i][j]);
            }
    printf("%d\n", f[n][n]);
    return 0;
}

方格取数原题链接

1027. 方格取数 - AcWing题库

方格取数代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;

int n;
int w[N][N];
int f[N*2][N][N];

int main(){
    scanf("%d",&n);
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c){
        w[a][b]=c;
    }
    for(int k=2;k<=n+n;k++)
        for(int i1=1;i1<=n;i1++)
            for(int i2=1;i2<=n;i2++)
            {
                int j1=k-i1, j2=k-i2;
                if(j1>=1 && j1<=n && j2>=1 && j2<=n)
                {
                    int t=w[i1][j1];
                    if(i1!=i2) t+=w[i2][j2];
                    int &x = f[k][i1][i2];
                    x = max(x, f[k-1][i1-1][i2-1]+t);
                    x = max(x, f[k-1][i1-1][i2]+t);
                    x = max(x, f[k-1][i1][i2-1]+t);
                    x = max(x, f[k-1][i1][i2]+t);
                }
            }
    printf("%d\n",f[n+n][n][n])
    return 0;
}