八年级学生做的简易网站,北京做网站公司排名浩森宇特,百度贴吧官网首页,乐清联科网站建设给你一个 m x n 的整数矩阵 points #xff08;下标从 0 开始#xff09;。一开始你的得分为 0 #xff0c;你想最大化从矩阵中得到的分数。
你的得分方式为#xff1a;每一行 中选取一个格子#xff0c;选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。
然…给你一个 m x n 的整数矩阵 points 下标从 0 开始。一开始你的得分为 0 你想最大化从矩阵中得到的分数。
你的得分方式为每一行 中选取一个格子选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。
然而相邻行之间被选中的格子如果隔得太远你会失去一些得分。对于相邻行 r 和 r 1 其中 0 r m - 1选中坐标为 (r, c1) 和 (r 1, c2) 的格子你的总得分 减少 abs(c1 - c2) 。
请你返回你能得到的 最大 得分。
abs(x) 定义为
如果 x 0 那么值为 x 。 如果 x 0 那么值为 -x 。
示例 1
输入points [[1,2,3],[1,5,1],[3,1,1]] 输出9 解释 蓝色格子是最优方案选中的格子坐标分别为 (0, 2)(1, 1) 和 (2, 0) 。 你的总得分增加 3 5 3 11 。 但是你的总得分需要扣除 abs(2 - 1) abs(1 - 0) 2 。 你的最终得分为 11 - 2 9 。 解题思路
数组定义
dp[i]代表在数组的最后一行选择第i列格子时的最大得分
状态转移
dp[i]只由上一行决定朴素的想法是对于每一个dp[i]都遍历上一行的所有值找出减去abs(c1 - c2)最大的那个得分但是我们可以进行优化只维护上一行中位于i左边的最大得分lMax和i右边的最大得分rMax通过在线性时间内扫描一遍i的同时维护lMax和rMax而dp[i]max(t[i],lMax-1,rMax-1)(t[i]为上一行的dp[i])
代码
class Solution {public long maxPoints(int[][] points) {int mpoints[0].length,npoints.length;long[] dp new long[m];for (int i0;in;i){long lMax0,rMax0;long[] t Arrays.copyOf(dp, m);for (int j0;jm;j){lMaxMath.max(lMax-1,dp[j]);t[j]Math.max(t[j],lMax);}for (int jm-1;j0;j--){rMaxMath.max(rMax-1,dp[j]);t[j]Math.max(t[j],rMax);}for (int j0;jm;j){t[j]points[i][j];}dpt;}long res0;for (int j0;jm;j){res Math.max(res,dp[j]);}return res;}
}
