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])≤100

0≤matrix[i][j]≤10 ^5
 
样例
样例 1

输入：
[[1, 2],
 [3, 4]]
输出： 6
说明 2 + 4 = 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路

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

答案

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30