题解 | #牛妹的礼物#

#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    int selectPresent(vector<vector<int> >& presentVolumn) {
        // write code here
        int N=presentVolumn.size();
        int M=presentVolumn[0].size();
        vector<vector<int>> dp(N,vector<int>(M,0));
        // 想法：dp[i][j]=min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] )+presentVolumn[i][j]
        // 首先初始化第一行和第一列
        dp[0][0]=presentVolumn[0][0];
        for (int j=1; j<M; j++) {
            dp[0][j]=presentVolumn[0][j]+dp[0][j-1];        
        }
        for (int i=1; i<N; i++) {
            dp[i][0]=presentVolumn[i][0]+dp[i-1][0];
        }
        // 开始遍历
        for (int i=1; i<N; i++) {
            for (int j=1; j<M; j++) {
                int minPath=min(dp[i-1][j-1], dp[i-1][j]);
                minPath=min(minPath,dp[i][j-1]);
                dp[i][j]=minPath+presentVolumn[i][j];
            }
        }
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                cout<<dp[i][j];
            }
        }
        return dp[N-1][M-1];
    }
};

动态规划，dp[i][j]表示到(i,j)位置的礼物体积和，有dp[i][j]=min( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] )+presentVolumn[i][j]

但是要注意解决好第一行和第一列的初始化问题。