方格取数

题目描述

算法：

DP(远古代码，没有注释)

C++ 代码

·#include <bits/stdc++.h>
·#include <iostream>
·#include <cstdio>
·#include <string.h>
·#include <cstring>
·#include <queue>
·#include <vector>
·#include <algorithm>
·#include <iomanip>
·#include <set>
·#include <stdlib.h>
·#include <math.h>
·using namespace std;
·long long M=-1000000;
·long long dp[1005][1005],a[1005][1005],x[1005],y[1005];
·int main () {
·    int n,m;
·    cin>>n>>m;
·    for(int i=1;i<=n;i++){
·       for(int j=1;j<=m;j++){
·            cin>>a[i][j];
·            if(j==1){
·                dp[i][j]=dp[i-1][j]+a[i][j];
·            }else{
·               dp[i][j]=M;
·           }
·        }
·   }
·    for(int j=2;j<=m;j++){
·        x[1]=dp[1][j-1]+a[1][j];
·        for(int i=2;i<=n;i++){
·           x[i]=max(x[i-1],dp[i][j-1])+a[i][j];
·       }
·        y[n]=dp[n][j-1]+a[n][j];
·        for(int i=n-1;i>=1;i--){
·           y[i]=max(y[i+1],dp[i][j-1])+a[i][j];
·       }
·        for(int i=1;i<=n;i++){
·           dp[i][j]=max(x[i],y[i]);
·       }
·    }
·    cout<<dp[n][m];
·    return 0;
·}