AcWing 1018 最低通行费 题解 （动态规划—DP—线性DP）

注意：状态转移时注意边界问题，需要加特判

#include
#include
#include

using namespace std;


const int N = 110, INF = 1e9;

int a[N][N];
int h[N][N];
int n;

int main()
{
    cin>>n;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            cin>>a[i][j];
        }
    }
    
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(i == 1 && j == 1) h[i][j] = a[i][j];
            else{
                h[i][j] = INF;
                if(i > 1) h[i][j] = min(h[i][j], h[i - 1][j] + a[i][j]);
                if(j > 1) h[i][j] = min(h[i][j], h[i][j - 1] + a[i][j]);
            }
        }
    }
    
    cout<