引言

作为本人DP的引路题，我想分享一下DP的使用条件，以及DP到底做了什么？DP为什么那么神奇？

1. DP源自递推。
   摘自《算法竞赛进阶指南》:动态规划算法把原问题视作若干个重叠的子问题的逐层递进，每个子问题的求解过程都构成一个”阶段”,在完成前一个阶段的计算后，动态规划才会执行下一阶段。
2. DP使用的条件。
   DP的使用条件为”无后效性”。即已经求解的子问题不受后续阶段影响。
3. DP为什么那么神奇（高效）？
   总而言之一句话：已经做过考虑的最优决策无需再做。

本题算法:线性DP O(r * c)

因为只能想东或者向南，所以每一次走到的点，一定不会被重复走到。这很好证明所以证明省略。且只能被上面一格的点或者左边一格的点走到。所以状态计算迎刃而解。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int g[N][N];
int f[N][N];

int main(){

    ios :: sync_with_stdio(false);
    cin.tie(0);

    int T;

    cin >> T;

    while(T--)
    {
        int r,c;
        cin >> r >> c;

        f[0][0] = 0;

        for(int i=0;i<r;i++)
            for(int j=0;j<c;j++)
                cin >> g[i][j];

        for(int i=0;i<r;i++)
            for(int j=0;j<c;j++)
            {
                if(i == 0 && j == 0)
                    f[i][j] = g[i][j];
                else
                {
                    int t = 0;
                    if(i) t = f[i - 1][j];
                    if(j) t = max(t,f[i][j - 1]);
                    f[i][j] = t + g[i][j];

                }
            }

        cout << f[r - 1][c - 1] << endl;
    }

    return 0;
}