北京网站如何制作,wordpress导入火车头,天津网站建设网站排名优化,我的网站域名是什么Problem: LCR 166. 珠宝的最高价值 文章目录 解题思路思路解题方法复杂度Code 解题思路 思路
改题目与本站64题实质上是一样的#xff0c;该题目在64题的基础上将求取最小路径和改成了求取最大路径和。具体实现思路如下#xff1a; 1.定义一个int类型的二维数组dp大小为给定… Problem: LCR 166. 珠宝的最高价值 文章目录 解题思路思路解题方法复杂度Code 解题思路 思路
改题目与本站64题实质上是一样的该题目在64题的基础上将求取最小路径和改成了求取最大路径和。具体实现思路如下 1.定义一个int类型的二维数组dp大小为给定矩阵frame的行数与列数。该数组用于记录每个当前阶段的最大路径和也是本题目的最大价值 2.动态转移方程为**dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]) frame[i][j];**即当前位置也可以记作阶段最大值每次取出其上方和左侧的较大值的一个与当前frame位置值作和 3.由于dp数组中第一行与第一列无法直接执行动态转移方程要对其初始化第一行每个位置值为依次向右累加第一列每个位置值为依次向下累加 3.最后返回dp数组中的最后一个值即可。 解题方法 1.定义数组frame的行数rows与列数columns并定义一个int变量temp用于记录累加和 2.定义并初始化int类型数组dp初始化为new int[rows][colunms] 3.初始化dp的第一行与第一列在for循环中使temp依次累加当前第一行列位置的值并赋值给当前dp数组位置 4.从dp数组的第二行索引为1开始执行动态转移方程dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]) frame[i][j];最后返回dp[rows - 1][columns - 1]; 复杂度
时间复杂度: O ( M N ) O(MN) O(MN),其中 M M M为数组frame的行数, N N N为其列数 空间复杂度: O ( M N ) O(MN) O(MN) Code
class Solution {/*** The maximum path sum is obtained using dynamic programming** param frame Given matrix* return int*/public int jewelleryValue(int[][] frame) {int rows frame.length;int columns frame[0].length;int temp 0;//Records the current maximum path sumint[][] dp new int[rows][columns];//Handle the first row and columnfor (int i 0; i columns; i) {temp frame[0][i];dp[0][i] temp;}temp 0;for (int j 0; j rows; j) {temp frame[j][0];dp[j][0] temp;}//Dynamic transfer equationfor (int i 1; i rows; i) {for (int j 1; j columns; j) {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]) frame[i][j];}}return dp[rows - 1][columns - 1];}
}
