题解 | #LP钱不够#动态规划新手版

思路：

00 01 02 03 04

10 11 12 13 14

20 21 22 23 24

30 31 32 33 34

40 41 42 43 44

基值：对于任意位置Aij(假如是11）， 它的最小花费由Max{10， 01}决定。你想呀，吃货只能往下走， 或者往右走，按照逆向思维，你只能看到吃货从上边来，或者从左边来。

特殊位置：对于第0行（00， 01 ， 02， ..), 和第0列（00， 10， 20， ..）， 站在这个位置（第0行）只能看到吃货从左边来， 就没有从上边来的，因为没有地。同样的，站在第0列，只能看到吃货从上边来，而没有从左边来的。所以，00位置的花费是固定的， 01位置的花费只由00位置决定，即01位置的花费是 00+01。 相同的， 02位置的花费只由01位置决定，即02位置的花费是 01+02.在列上也是如此。

通过特殊位置（第0行， 第0列）， 我们可以一层一层往44位置推。记住，特殊位置的值已经得出。

所以， 11位置的值为 Max{10， 01}， 21位置的值为 Max{20， 11}， ....不过，只有你先推出 11位置的花费， 才能推21位置的花费， 12位置的花费。也就是说， 你若是按照行优先的原则推， 且从左往右，你最终能推出 44 位置的最小花费。

#include<vector>
#include<cmath>
using namespace std;
int main()
{
    int x;
    int n;
    cin>> x;
    for(int k = 0; k < x - 1; ++k)
    {
        cin>> n;
        vector<vector<int>> v(n, vector<int>(n));
        int i, j;
        for(i = 0; i < n; ++i)
        {
            for(j = 0; j < n; ++j)
            {
                cin>> v[i][j];
            }
        }
        for(i = 1; i < n; ++i)
        {
            v[i][0] = v[i][0] + v[i - 1][0];
            v[0][i] = v[0][i] + v[0][i - 1];
        }
        for(i = 1; i < n; ++i)
        {
            for(j = 1; j < n; ++j)
            {
                v[i][j] += min(v[i - 1][j], v[i][j - 1]);
            }
        }
        cout<<v[n - 1][n - 1]<<'\n';
    }
    
    //按照格式要求， 最后一次求解独立出来，这里增大了代码规模
    cin>> n;
        vector<vector<int>> v(n, vector<int>(n));
        int i, j;
        for(i = 0; i < n; ++i)
        {
            for(j = 0; j < n; ++j)
            {
                cin>> v[i][j];
            }
        }
        for(i = 1; i < n; ++i)
        {
            v[i][0] = v[i][0] + v[i - 1][0];
            v[0][i] = v[0][i] + v[0][i - 1];
        }
        for(i = 1; i < n; ++i)
        {
            for(j = 1; j < n; ++j)
            {
                v[i][j] += min(v[i - 1][j], v[i][j - 1]);
            }
        }
        cout<<v[n - 1][n - 1];
}