有趣的网站代码,在线咨询,深圳华强北封闭了吗,全屏网站设计技巧题目
https://www.lintcode.com/problem/567
给定一个矩阵matrix#xff0c;
matrix[i][j]表示你到达第i行第j列可以得到的分数#xff0c;现在你要用第0行任意一点出发#xff0c;从每行里找到一个点进行跳跃#xff0c;每次从(i,j)到(i1,k)跳跃需要消耗∣j−k∣的分数
matrix[i][j]表示你到达第i行第j列可以得到的分数现在你要用第0行任意一点出发从每行里找到一个点进行跳跃每次从(i,j)到(i1,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,mmatrix[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) {maxMath.max(max,dp[n-1][i]);}return max;}
}
