洛谷P7074 [CSP-J 2020] 方格取数一题的题解

想必大家做早期码农时都遇到过这样一道题：
一个人从矩形左上角出发到右下角的终点有几种走法？（他只能往右或往下）
假设这人到了一个格点，那他只会是从上面掉下来或左边移过来的，所以他到此点走法数等于他上面那格加上左边那格的走法数。
这道题的解法是类似的当时我真没想到自己手搓了一道dp。但是需要先预处理第一列，之后每一列从下往上、从上往下求走法数，再取最大值。

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1005][1005];
long long dp[1005][1005];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
dp[i][j]=–1e18;
}
}
//第一列 从上往下
dp[0][0]=a[0][0];
for(int i=1;i<n;i++)
{
dp[i][0]=dp[i–1][0]+a[i][0];
}
//处理每一列
for(int j=1;j<m;j++)
{
//从上往下
long long d[1005];
d[0]=dp[0][j–1]+a[0][j];
for(int i=1;i<n;i++)
{
d[i]=max(dp[i][j–1],d[i–1])+a[i][j];
}
//从下往上
long long u[1005];
u[n–1]=dp[n–1][j–1]+a[n–1][j];
for(int i=n–2;i>=0;i—)
{
u[i]=max(dp[i][j–1],u[i+1])+a[i][j];
}
//最大值
for(int i=0;i<n;i++)
{
dp[i][j]=max(d[i],u[i]);
}
}
cout<<dp[n–1][m–1];
return 0;
}