最低通行费

这题和方格取数一样, 都是2d的dp问题.

#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;
}