跑图类dp问题 | 比企谷八幡

算法 dp 数字三角形模型

算法 dp

发布日期: 2020-08-03

更新日期: 2020-08-05

文章字数: 646

阅读时长: 2 分

一.跑图类dp问题的定义

对于数字三角形模型(跑一个金字塔求最值)所演变出来的一系列跑图求最值的模型,我统称为跑图类dp问题

二.经典案例(传纸条)

https://www.acwing.com/activity/content/problem/content/1286/1/

1.解法分析

本题可以看作是两个人同时从起点出发(原因稍微想一下就明白了),按照闫式分析法，dp[k][i1][i2]表示的含义是走k步,两个人分别走到第i1,i2行的时候dp的最大值,那么从当前状态dp[k][i1][i2]易得：上一个状态的集合dp[k-1] 有四个元素,分别是第一个人和第二个人从向右走和向下走到(i1,k-i1),(i2,k-i2),经过排列组合2X2共有四个元素

2.AC代码：

//这题直接套方格取数的模板即可就最后输出的时候要注意以下,出发点和终点会重合
#include<bits/stdc++.h>
using namespace std;
const int N=101; 
int dp[N][N][N];
int g[N][N];
int mx(int a,int b,int c,int d) 
{
    a=max(a,b);
    a=max(a,c);
    a=max(a,d);
    return a;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }
    //循环这里可以直接i1和i2<=n即可,但是为了效率更高,我用了min.由于合法的dp值必然是从合法的dp值转移过来,所以不必担心i1,i2超过k的问题
    for(int k=1;k<=n+m;k++){
        for(int i1=1;i1<=n;i1++){
            for(int i2=1;i2<=n;i2++){
                if(i1==i2)
                    continue;
                else{
                    dp[k][i1][i2]=mx(dp[k-1][i1-1][i2-1],dp[k-1][i1-1][i2],dp[k-1][i1][i2-1],dp[k-1][i1][i2])+g[i1][k-i1]+g[i2][k-i2];
                }
            }
        }
    }
    //因为他们仅仅只在终点和起点会重合,且这两个点的g值为0,所以算到n+m-1步即可
    cout<<dp[n+m-1][n-1][n];
}