最低通行费
这题和方格取数一样, 都是2d的dp问题.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <vector> #include <climits> #include <algorithm> using namespace std; #define fio ios::sync_with_stdio(0);cin.tie(0) #define nfio cin.tie(0) int m[101][101]; int dp[101][101]; int main() { fio; nfio; int N; cin >> N; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { int t; cin >> t; m[i][j] = t; } } auto dfs =[&](auto dfs, int i, int j) -> int { if (dp[i][j] > 0) { return dp[i][j]; } if (i == 0 || j == 0) { return INT_MAX / 2; } if (i == 1 && j == 1) { return m[i][j]; } int res = INT_MAX; res = min(res, dfs(dfs, i - 1, j) + m[i][j]); res = min(res, dfs(dfs, i, j - 1) + m[i][j]); dp[i][j] = res; return res; }; cout << dfs(dfs, N, N) << endl; return 0; } |