动态规划（5）路径问题--剑指offer -珠宝的最大值

题目：      现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1：

输入：frame = [[1,3,1],[1,5,1],[4,2,1]]
输出：12
解释：路径 1→3→5→2→1 可以拿到最高价值的珠宝

1.状态表示：

      从  dp[i][j]表示：到达【i，j】位置1时候，此时的最大值

2.状态转移方程：

      dp[i][j]=max(dp[i-1][j],dp[i][j-1])+g[i][j]

3.初始化：

    1.里面的值，要保证后面的填表是正确的

    2.下标的映射

4.填表顺序：

从上往下填每一行

每一行从左往右

5.返回值：

dp【m】【n】

public class Solution {public int jewelleryValue(int[][] frame){//1.创建dp表//2.初始化//3.填表//4.返回值int m=frame.length,n=frame[0].length;int[][]dp=new int[m+1][n+1];for (int i=1;i<=m;i++)for (int j=1;j<=n;j++)dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])+frame[i-1][j-1];return dp[m][n];}public static void main(String[] args) {Solution solution=new Solution();int[][]frame={{1,3,1},{1,5,1},{4,2,1}};System.out.println(solution.jewelleryValue(frame));}
}