[TIOJ] 1268. 得分高手 (Master)

題目連結:http://tioj.infor.org/problems/1268

---

想了兩下後發現可以DP，狀態也很簡單就是$dp[i][j]$代表結尾在$(i,j)$時的最大值，轉移就只要$dp[i][j]=max(0, dp[i-1][j], dp[i][j-1])+mtx[i][j]$其中mtx代表原始的數字。

#include <bits/stdc++.h>
using namespace std;
const int N = 3000 + 5;

int mtx[N][N], dp[N][N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m, ans=0; cin>>n>>m;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
		cin>>mtx[i][j];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i-1 >= 0) dp[i][j] = max(dp[i-1][j], dp[i][j]);
			if(j-1 >= 0) dp[i][j] = max(dp[i][j-1], dp[i][j]);
			dp[i][j]+=mtx[i][j];
			ans = max(ans, dp[i][j]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}