题目

重点是题目的性质，限制 2N-1 步，故只能向右向下走，否则出不去。利用此性质转化为 K 取方格数（K = 1）。

注意

本题特殊在dp分析，状态设计的时候，要注意状态的条件。

dp 分析

• 状态表示
  • 集合
    • 所有…的集合
    • 条件：边界、前几个、后几个、体积小于…、时间小于…等
  • 属性：max、min ......
• 状态计算（状态之间的关系）：主要看最后一步到当前状态的状态转移。

#include<iostream>

#define _rep_le(i, a, b) for(int i = (a); i <= (b); ++ i)
#define _rep_lt(i, a, b) for(int i = (a); i < (b); ++ i)
#define _rrep_ge(i, a, b) for(int i = (b); i >= (a); -- i)
#define _rrep_gt(i, a, b) for(int i = (b); i > (a); -- i)

using namespace std;

const int N = 1e2 + 5;

int arc[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    _rep_le(i, 1, n) {
        _rep_le(j, 1, n) {
            cin >> arc[i][j];
            // if(arc[i-1][j] > arc[i][j-1]) {
            //     cout << "i:" << i << "  j:" << j 
            //         << " pick arc[" << i << "][" << j-1 << "]:" << arc[i][j-1] << endl;
            // } else {
            //     cout << "i:" << i << "  j:" << j 
            //         << " pick arc[" << i-1 << "][" << j << "]:" << arc[i-1][j] << endl;
            // }
            if(i - 1 == 0) arc[i][j] += arc[i][j - 1];
            else if(j - 1 == 0) arc[i][j] += arc[i - 1][j];
            else arc[i][j] += min(arc[i-1][j], arc[i][j-1]);
        }
    }

    cout << arc[n][n];

    return 0;
}