e878 - Q2 得分高手

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個 n x m 的矩陣，矩陣中的每個元素代表一個分數。要求從左上角 (0, 0) 到右下角 (n-1, m-1) 的路徑，每次只能向右或向下移動，使得路徑上的分數總和最大。

解題思路

本題可以使用動態規劃 (Dynamic Programming) 解決。定義 dp[i][j] 為從 (0, 0) 到 (i, j) 的最大分數總和。 初始化 dp[0][0] = a[0][0]。 對於每個 (i, j)，如果 i > 0，則 dp[i][j] = max(dp[i-1][j] + a[i][j], dp[i][j])，表示從上方移動到 (i, j)。 如果 j > 0，則 dp[i][j] = max(dp[i][j-1] + a[i][j], dp[i][j])，表示從左方移動到 (i, j)。 最後，dp[n-1][m-1] 就是從 (0, 0) 到 (n-1, m-1) 的最大分數總和。 程式碼中，從 (n-1, m-1) 反向填充 dp 表格，可以節省空間。

複雜度分析

• 時間複雜度: O(n*m)
• 空間複雜度: O(n*m)

程式碼

#include <iostream>
using namespace std;
int dp[3005][3005],a[3005][3005],n,m,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			cin >> a[i][j];
		}
	}
	for(int i=n-1;i>=0;--i){
		for(int j=m-1;j>=0;--j){
			dp[i][j]=a[i][j];
			if(i!=n-1){
				dp[i][j]=max(dp[i+1][j]+a[i][j],dp[i][j]);
			}
			if(j!=m-1){
				dp[i][j]=max(dp[i][j+1]+a[i][j],dp[i][j]);
			}
			ans=max(dp[i][j],ans);
		}
	}
	cout << ans;
}