1937. 带成本的最大得分点数
内容提要
给定一个m x n的整数矩阵，每一行选择一个单元格，选择的单元格与上一行选择的单元格的距离过远会扣分，求能获得的最大分数。使用动态规划，定义dp数组表示选择每个单元格时的最大分数，初始化dp数组，计算每一行的dp值，更新dp数组，返回最后一行的最大值。
延伸解读
动态规划状态定义与初始化
文章定义dp[i][j]为选择第i行第j列单元格时的最大得分。由于第一行没有上一行，初始化dp[0][j]与points[0][j]相同。这种定义直接对应问题要求：每行选一个单元格，且相邻行选择会产生距离扣分。初始化步骤为后续行计算提供了基础，确保状态转移从第一行开始正确累积得分。
利用左右数组优化转移
直接计算dp[i][j]需要枚举上一行所有列，时间复杂度为O(m×n²)。文章引入left和right辅助数组：left[j]存储仅考虑从左侧转移的最大值，right[j]存储仅考虑从右侧转移的最大值。这样每行只需线性扫描两次即可得到每个列的最优前驱，将转移优化到O(n)，整体复杂度降为O(m×n)，适合大矩阵。
时间复杂度和适用性
文章指出该方法的时间复杂度为O(m×n)，在给定约束m,n≤10^5且m×n≤10^5下非常高效。空间上使用二维dp数组，也可优化为一维。这种动态规划加左右扫描的技巧是处理带距离惩罚的行选择问题的典型方法，能有效避免暴力枚举带来的性能瓶颈。
Q&A
如何在给定的矩阵中最大化得分？
通过选择每一行的一个单元格，并计算相邻行之间的距离惩罚来最大化得分。
动态规划在这个问题中如何应用？
使用动态规划定义dp数组，dp[i][j]表示选择第i行第j列单元格时的最大分数。
如何初始化dp数组？
dp数组的第一行初始化为与points矩阵的第一行相同，因为没有前一行可供计算惩罚。
在计算每一行的dp值时，如何优化计算？
使用辅助数组left和right来分别存储从左侧和右侧过渡的最大值，从而优化计算。
最后一行的最大值如何得到？
返回dp数组最后一行的最大值，即为可以获得的最大得分。
该算法的时间复杂度是多少？
该算法的时间复杂度为O(m × n)，适合处理大矩阵。
