/** * 动态规划公式dp[i][j]= min{dp[i][j-1],dp[i-1][j],d[i-1][j-1]} * */
public class Solution { /** * * @param presentVolumn int整型二维数组 N*M的矩阵,每个元素是这个地板砖上的礼物体积 * @return int整型 */ public int selectPresent (int[][] presentVolumn) { // 数组大小为0时返回0 if (presentVolumn.length == 0 || presentVolumn[0].length == 0){ return 0; } int n = presentVolumn.length; int m = presentVolumn[0].length; // 初始化数组 int dp[][] = presentVolumn; // 初始化第一行 for (int i = 1; i < n; i++){ dp[i][0] += dp[i - 1][0]; } // 初始化第一列 for (int j = 1; j < m; j++){ dp[0][j] += dp[0][j - 1]; } // 当前位置最小值为(左上,上,左中最小值加上当前值) for (int i = 1; i < n; i++){ for (int j = 1; j < m; j++){ dp[i][j] += Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]); } } return dp[n- 1][m - 1]; } }