d378 - 最小路徑
題目描述
題目要求找出一個矩陣中，從左上角到右下角的最短路徑，路徑只能向右或向下移動，路徑的成本是沿途經過的單元格值的總和。
解題思路
本題可以使用動態規劃 (Dynamic Programming) 解決。定義 dp[i][j] 為從左上角 (0, 0) 到 (i, j) 的最小路徑成本。
初始化 dp[0][0] 為 a[0][0]。
對於第一行，dp[0][j] = dp[0][j-1] + a[0][j]。
對於第一列，dp[i][0] = dp[i-1][0] + a[i][0]。
對於其他單元格，dp[i][j] = min(dp[i-1][j] + a[i][j], dp[i][j-1] + a[i][j])。
最後，dp[y-1][x-1] 就是從左上角到右下角的最短路徑成本。
複雜度分析
- 時間複雜度: O(N*M)，其中 N 是矩陣的行數，M 是矩陣的列數。因為需要遍歷整個矩陣一次來計算 dp 值。
- 空間複雜度: O(NM)，因為需要一個大小為 NM 的 dp 矩陣來存儲中間結果。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int x,y,ca=0;
while(cin >> y >> x){
int a[y][x],dp[y][x];
for(int i=0;i<y;++i)
for(int j=0;j<x;++j){
cin >> a[i][j];
dp[i][j]=0;
}
dp[0][0]=a[0][0];
for(int i=1;i<y;++i)
dp[i][0]=a[i][0]+dp[i-1][0];
for(int j=1;j<x;++j)
dp[0][j]=a[0][j]+dp[0][j-1];
for(int i=1;i<y;++i)
for(int j=1;j<x;++j)
dp[i][j]=min(a[i][j]+dp[i-1][j],a[i][j]+dp[i][j-1]);
cout << "Case #" << ++ca << " :\n" << dp[y-1][x-1] << "\n";
}
}