题解 | #牛妹的礼物#

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();
        int *dp = new int[n*m];
        dp[0]=presentVolumn[0][0];
        for(int i =1; i<n;i++)
        {
            dp[i*m]=dp[(i-1)*m]+presentVolumn[i][0];
//             cout<<dp[i*m]<<" ";
        }
        for(int i =1; i<m;i++)
        {
            dp[i]=dp[i-1]+presentVolumn[0][i];
        }
        for(int i =1; i<n;i++)
        {
            for(int j =1; j<m;j++)
            {
                int min1=min(dp[i*m+j-1],dp[(i-1)*m+j]);
                min1 = min(min1,dp[(i-1)*m+j-1]);
                dp[i*m+j] = min1+presentVolumn[i][j];
            }
        }
//         for(int i =0; i<n;i++)
//         {
//             for(int j =0; j<m;j++)
//             {
//                 cout<<dp[i*m+j]<<" ";
//             }
//             cout<<endl;
//         }
        return dp[m*n-1];
        /*
        1 2 3
        2 3 4
        */
    }
};