牛妹的礼物

 /**
 * 动态规划公式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];
    }
}