在⼀个m × n的棋盘的每⼀格都放有⼀个礼物每个礼物都有⼀定的价值价值⼤于 0。你可以从棋盘的左上⻆开始拿格⼦⾥的礼物并每次向右或者向下移动⼀格、直到到达棋盘的右下⻆。给定⼀个棋盘及其上⾯的礼物的价值请计算你最多能拿到多少价值的礼物如输⼊这样的⼀个⼆维数组txet[ [1,3,1], [1,5,1], [4,2,1] ]那么路径 1→3→5→2→1 可以拿到最多价值的礼物价值为 12思路及解答基础动态规划这道题其实⼀看就知道是动态规划棋盘中的每个⼩格⼦都是和上⽅或者左⽅的格⼦有关。既然是动态规划那么我们先定义状态dp[i][j]表示到达(i,j)位置时能获得的最大礼物价值状态转移dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]javapublic int maxValue(int[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length, n grid[0].length; int[][] dp new int[m][n]; // 初始化起点 dp[0][0] grid[0][0]; // 初始化第一行只能从左边来 for (int j 1; j n; j) { dp[0][j] dp[0][j-1] grid[0][j]; } // 初始化第一列只能从上边来 for (int i 1; i m; i) { dp[i][0] dp[i-1][0] grid[i][0]; } // 填充其余位置 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] Math.max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } return dp[m-1][n-1]; }每个位置的计算只依赖左边和上边的结果通过双重循环自左上向右下填充整个dp表时间复杂度O(mn)空间复杂度O(mn)空间优化动态规划观察发现当前行只依赖上一行可以使用一维数组进行空间优化利用dp[j]在更新前存储上一行第j列的值更新后存储当前行第j列的值实现空间复用dp[j]表示当前行第j列的最大价值滚动更新javapublic int maxValue(int[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length, n grid[0].length; int[] dp new int[n]; // 初始化第一行 dp[0] grid[0][0]; for (int j 1; j n; j) { dp[j] dp[j-1] grid[0][j]; } // 处理后续行 for (int i 1; i m; i) { // 更新第一列 dp[0] grid[i][0]; for (int j 1; j n; j) { // dp[j]代表上一行第j列的值从上方来 // dp[j-1]代表当前行第j-1列的值从左边来 dp[j] Math.max(dp[j], dp[j-1]) grid[i][j]; } } return dp[n-1]; }时间复杂度O(mn)空间复杂度O(n)原地修改动态规划最优解修改原数组直接使用grid数组作为dp表避免额外空间分配javapublic int maxValue(int[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length, n grid[0].length; // 初始化第一行 for (int j 1; j n; j) { grid[0][j] grid[0][j-1]; } // 初始化第一列 for (int i 1; i m; i) { grid[i][0] grid[i-1][0]; } // 填充其余位置 for (int i 1; i m; i) { for (int j 1; j n; j) { grid[i][j] Math.max(grid[i-1][j], grid[i][j-1]); } } return grid[m-1][n-1];