力扣每日一题 1937. 扣分后的最大得分

发布时间:2024年01月17日

?本题中其实本质是一个线性DP,根据行数从上往下选,先选第一层的一个数,再选第二层,最后再选到最后一层,但是本题中我们有个重要的条件,就是选出最大得分,那么每层选最大,在往下选最大,能得到最大得分吗?不一定,这个其实是有点贪心,其实不是,因为我们还有一个条件,abs(j - k),j是当前坐标的列号,k是上层选的坐标的列号,那么这个不能确定的话,我们是不能从前面最大得分,推导到下层的最大得分,假如说没有abs(j - k)这个条件,我们可以从前面i - 1层中选出最大的,到前面i层中选出最大的。正因为这个条件abs(j - k)这个条件的不确定性

导致我们无法进行我说的那样推导,那么有原因了,我们就知道该问题的本质就是解决abs(j -k),那么把abs(j - k)这个特性解决掉就行。

f[i][j]代表选了该坐标(i,j)后得到的最大分数,

首先要解决abs(j - k)之前,我们先把状态转移方程写出来

//注意这里的是n行m列

f[i][j] = \sum0<= k <= m max(f[i][j],f[i - 1][k] + abs(j - k))+ a[i][j];

那么变一下式子

后面默认带有\sum

f[i][j] =?max(f[i][j],f[i - 1][k])+abs(j - k) + a[i][j];

现在我们有了这个式子,那么我们就可以来解决abs(j - k)

abs(j - k)? 可以变成,j - k和k - j

那么f[i][j] =?max(f[i][j],f[i - 1][k])+abs(j - k)这个式子就可以变成两种情况

1 .? f[i][j] = j? - k + f[i - 1][k] + a[i][j];

2.? ?f[i][j] = k - j + f[i - 1][k] + a[i][j];

那么删掉之后我们要确保j - k和k - j是正数,所以我们就已经确定了k的范围,

当为j - k时,k <= j,当为k - j时,k > j.这就划分出了上层的左右部分了,

那么我们就知道第一个状态就只能选上层的k <= j这些列的其中一个数了

同理第二个也是

然后我们在回头想想我前面说的那个部分,我们现在只是可以确定选哪些列了,但是我们还是不知道怎么选最大的,这里我们就可以用前缀思想去解决这个问题了,并且我们的前缀是要实时变换的,而且我们转移的时候只跟上一层有关联,上一层是不是只有f[i - 1][k] - k和f[i - 1][k] +?k,

那么其实我们只需要记录一下0 ~ j之前最大的,和记录一下j + 1 ~ m - 1之间最大的就行,一边推导一边判断就行,用前缀思想maxl = max(maxl,f[i - 1][j] + j),同理右边也是

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) 
    {
         int n = points.size();
         int m = points[0].size();


         long long f[n + 10][m + 10];
         memset(f,0,sizeof(f));
         //f[i][j] = a[i][j] - j + maxv_prev
         for(int i = 0;i < m;i++) f[0][i] = points[0][i];
         long long maxl = -0x3f3f3f3f;
         long long maxr = -0x3f3f3f3f;
         for(long long i = 1;i < n;i++)
         {
             maxl = -0x3f3f3f3f;
             maxr = -0x3f3f3f3f;
            for(long long j = 0;j < m;j++)
            {
               maxl = max(maxl,f[i - 1][j] + j);
               f[i][j] = points[i][j] - j + maxl;
            } 
            for(long long k = m - 1;k >= 0;k--)
            {
               maxr = max(maxr,f[i - 1][k] - k);
               f[i][k] = max(f[i][k],points[i][k] + k + maxr);
            }
         }
         long long res = 0;
         for(long long i = 0;i < m;i++) res = max(res,f[n - 1][i]);
         return res;
    }
};

文章来源:https://blog.csdn.net/txh1873749380/article/details/135656788
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。