d482 - 方格取数
題目描述
題目描述一個 N x N 的方格，每個方格包含一個非負整數。要求從左上角 (0, 0) 到右下角 (N-1, N-1) 的路徑，只能向下或向右移動，並使得路徑上經過的方格數字總和最大。
解題思路
本題可以使用動態規劃 (Dynamic Programming) 解決。定義 dp[i][j] 為從 (0, 0) 到 (i, j) 的最大路徑和。
初始化 dp[0][0] 為 a[0][0]。
對於第一行和第一列，dp[i][0] 等於 dp[i-1][0] + a[i][0]，dp[0][j] 等於 dp[0][j-1] + a[0][j]。
對於其他方格，dp[i][j] 等於 max(dp[i-1][j] + a[i][j], dp[i][j-1] + a[i][j])，即從上方或左方到達 (i, j) 的最大路徑和加上當前方格的數字。
最終結果為 dp[n-1][n-1]。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
using namespace std;
int main(){
int n;
while(cin >> n){
int a[n][n],dp[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> a[i][j];
dp[i][j]=0;
}
}
dp[0][0]=a[0][0];
for(int i=1;i<n;i++){
dp[i][0]=a[i][0]+dp[i-1][0];
dp[0][i]=a[0][i]+dp[0][i-1];
}
for(int i=1;i<n;i++)
for(int j=1;j<n;j++)
dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);
cout << dp[n-1][n-1] << "\n";
}
}