珠宝的最高价值

题目链接链接: 珠宝的最高价值题目要求解题思路由于这道题是典型的动态规划通常动态规划的解题步骤是状态表示根据状态表示推导状态转移方程初始化 dp 表确定填表的顺序返回值1. 状态表示根据示例1 的信息 到达右下角位置时, 一路上拿到的所有宝石的总和是 最高价值那么状态表示 dp[ i ][ j ]:到达[ i , j ]位置时 一路上拿到的所有宝石的总和是 最高价值2. 根据状态表示推导状态转移方程状态转移方程通常是根据最近一步来进行推导的又根据题目取宝石的第2条规则 每次可以移动到右侧或下侧的相邻位置那么到达dp[ i ] [ j ]位置时有2条那宝石的路径 :从左边[ i , j - 1 ]到达[ i , j ]从上边[ i - 1 , j ]到达[ i , j ]又根据状态表示dp[ i ][ j ]: 到达[ i , j ]位置时 一路上拿到的所有宝石的总和是 最高价值那么 [ i , j ] 位置的最高价值 就可表示为 左边的拿宝石路径[ i , j - 1 ]的最高价值 [ i , j ]位置的宝石价值上边的拿宝石路径[ i - 1 , j ]的最高价值 [ i , j ]位置的宝石价值既然是最高价值那么可以推测出 要对以上2条路经 进行比较找出Max来保证到达[ i j ]位置时拿到的宝石总和是最高价值又根据以上推测 需要比较哪条拿宝石路径可以拿到 最高价值, 从而最终推导出状态转移方程 dp[ i ][ j ] Math.max( dp[ i - 1 ][ j ] , dp[ i ][ j - 1 ] ) frame[ i - 1 ][ j - 1 ]3. 初始化 dp 表初始化的目的 防止填表时越界访问使用动态规划的时候为了简化繁琐的初始化代码通常在 申请dp表数组时使用加入空位置的操作按照此题的要求也就是需要多开出1行和1列的空间。但是要注意加上多开出的空间要保证填dp表的值是正确的注意dp表的下标位置和 原数据下标位置的映射关系所以状态转移方程的最后是frame[ i - 1 ][ j - 1 ]的目的是保证dp表的下标位置和 原数据下标位置的映射关系的正确性由于题目给frame数组中的值已经是 宝石价值的表示了因此多开的空间初始化成0即可这里拿示例1 来举例dp表初始化4. 确定填表顺序从上到下填每一行从左到右填每一列5. 返回值return dp[ m ] [ n ]注m、n是frame数组的行数、列数代码实现classSolution{publicintjewelleryValue(int[][]frame){intmframe.length,nframe[0].length;//创建 dp 表int[][]dpnewint[m1][n1];//初始化 数组的默认值是0 所以没有初始化这步//填表for(inti1;im;i){for(intj1;jn;j){dp[i][j]Math.max(dp[i-1][j],dp[i][j-1])frame[i-1][j-1];}}//返回值returndp[m][n];}}