[数据结构与算法]Leetcode 1937 动态规划的优化（两次遍历）

$m\times n$ 的矩阵中每一行选择一个，得分只与相邻行的元素有关，可以采用动态规划的方法解决。
比较容易想到的建表方式：$dp[i][j]$ 表示选择矩阵第 $i$ 行，第 $j$ 列的元素时能够取得的得分最大值。状态转移方程：$$dp[i][j]=max(dp[i?1][j^{\prime }]+|j^{\prime }?j|)+nums[i][j]$$然而，每生成一个值都要在上一行中比较，找出最大的一个，其时间复杂度为 $O(m{n}^2)$，会超时，需要进一步优化。

要求最大值是一定需要遍历的，优化的重点在于：不再用 $n$ 次操作优化1个值，而是用 $n$ 次操作优化 $n$ 个值。
用一行中前一个值 $dp[i][j?1]$ 为基础，对前一行中选择上正上方的值 $dp[i?1][j]$ 还是之前的某一个值进行比较，选择较大的那一个。由于列之间的损失是可以传导的，比较时 $dp[i][j?1]$ 需减一，这样做出相同选择时结果就是一样的了。这样的操作（正向）只看到了当前列之前的选择，后面的部分没有考虑到，因此还要进行一次反向过程。

状态转移方程如下：
正向过程：$$dp[i][j]=max(dp[i][j?1]?1,dp[i?1][j])$$反向过程：$$dp[i][j]=max(dp[i][j+1]?1,dp[i?1][j])$$最后，$dp[i][j]=dp[i][j]+nums[i][j]$得到选择数 $nums[i][j]$ 时的最大得分。
时间复杂度为：$O(2mn)=O(mn)$

附上代码：

typedef long long ll;
class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        vector<vector<ll> > dp(points.size(), vector<ll>(points[0].size(), 0));
        ll maxim = 0;
        
        for(int i = 0; i<points[0].size(); i++) {
            dp[0][i] = points[0][i];
            maxim = max(maxim, dp[0][i]);
        }

        for(int i=1; i<points.size(); i++) {
            dp[i][0] = dp[i-1][0];
			//正向过程
            for(int j = 1; j < points[0].size(); j++) dp[i][j] = max(dp[i-1][j], dp[i][j-1]-1);
            //反向过程
            for(int j = points[0].size()-2; j >= 0; j--) dp[i][j] = max(dp[i][j], dp[i][j+1]-1);
			//加上数字本身，统计最大值
            for(int j = 0; j < points[0].size(); j++) {
                dp[i][j] += points[i][j];
                maxim = max(maxim, dp[i][j]);
            }
        }
        return maxim;
    }
};