lintcode 567 · 最大得分 【动态规划 中等 】

题目

https://www.lintcode.com/problem/567

给定一个矩阵matrix，
matrix[i][j]表示你到达第i行第j列可以得到的分数，现在你要用第0行任意一点出发，从每行里找到一个点进行跳跃，每次从(i,j)到(i+1,k)跳跃需要消耗∣j−k∣的分数，请问到最后一行以后，你最多可以得到多少分。1≤len(matrix),len(matrix[0])≤1000≤matrix[i][j]≤10 ^5样例
样例 1输入：
[[1, 2],[3, 4]]
输出： 6
说明 2 + 4 = 6.

思路

动态规划，下一行依赖上一行

答案

public class Solution {/*** @param matrix: the matrix* @return: the maximum score you can get*/public int maximumScore(int[][] matrix) {//简单的动态规划，认真读题目，看下面的代码//很容易看懂依赖关系int n = matrix.length,m=matrix[0].length;int[][] dp = new int[n][m];for (int j = 0; j < m ; j++) {dp[0][j] = matrix[0][j];}for (int i = 1; i <n ; i++) {for (int j = 0; j <m ; j++) {for (int k = 0; k <m ; k++) {dp[i][j] = Math.max(dp[i][j],dp[i-1][k]-Math.abs(j-k)+matrix[i][j]);}}}int max =Integer.MIN_VALUE;for (int i = 0; i < m; i++) {max=Math.max(max,dp[n-1][i]);}return max;}
}