​Leetcode 166.珠宝的最高价值​ 网格图dp C++实现

问题：Leetcode 166.珠宝的最高价值

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

算法1：递归 寻找子问题（超时）

受上图启发，定义 dfs ( i , j ) 表示从左上角到第 i 行第 j 列这个格子（记作  ( i , j ) ）的最大价值和。

分类讨论怎么到达 ( i , j )：

如果是从左边过来，则 dfs ( i , j ) = dfs ( i , j − 1 ) + frame [ i ] [ j ] ；
如果是从上边过来，则 dfs ( i , j ) = dfs ( i − 1 , j ) + frame [ i ] [ j ] 。

这两取最大值，得 dfs ( i , j ) = max ( dfs ( i , j − 1 ) , dfs ( i − 1 , j ) ) + frame [ i ] [ j ]
递归边界：当 i < 0 或 j < 0 时，返回 0，因为出界是没有价值的。也就是 dfs ( −1 , j ) = 0 , dfs ( i , − 1 ) = 0 。

递归入口：dfs(m−1,n−1)。

代码：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        function<int(int,int)>dfs = [&](int i,int j)->int{
            if(i < 0 || j < 0)  return 0;
            return max(dfs(i,j-1),dfs(i-1,j)) + frame[i][j];
        };
        return dfs(frame.size() - 1,frame[0].size() - 1);
    }
};

算法2：记忆化搜索

如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组（或哈希表）中；
如果一个状态不是第一次遇到，那么直接返回 memo 中保存的结果

代码：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(),n = frame[0].size();
        int memo[m][n]; // memo数组 存放记录
        memset(memo, 0, sizeof(memo)); // 初始化
        function<int(int,int)>dfs = [&](int i,int j)->int{
            if(i < 0 || j < 0)  return 0;
            int &res = memo[i][j];
            if(res) return res;
            return res = max(dfs(i,j-1),dfs(i-1,j)) + frame[i][j];
        };
        return dfs(m - 1,n - 1);
    }
};

算法3：1:1 翻译成递推

代码：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(),n = frame[0].size();
        int dp[m + 1][n + 1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++)
                dp[i + 1][j + 1] = max(dp[i + 1][j],dp[i][j + 1]) + frame[i][j];

        return dp[m][n];
    }
};

算法4：空间优化·方法一（两个数组，滚动数组）

由于 dp [ i + 1 ] 只依赖 dp [ i ] ，那么 dp [ i − 1 ] 及其之前的数据就没用了。

例如计算 dp [ 2 ] 的时候，数组 dp [ 0 ] 不再使用了。

那么干脆把 dp [ 2 ] 填到 dp [ 0 ] 中。同理，把 dp [ 3 ] 填到 dp [ 1 ] 中，dp [ 4 ] 填到 dp [ 0 ] 中，……

因此可以只用两个长为 n+1 的数组滚动计算。

代码：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(),n = frame[0].size();
        int dp[2][n + 1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++)
                dp[(i + 1) % 2][j + 1] = max(dp[(i + 1) % 2][j],dp[i % 2][j + 1]) + frame[i][j];

        return dp[m % 2][n];
    }
};

算法5：空间优化·方法二（一个数组）

举个例子，在计算 dp [ 1 ] [ 1 ] 时，会用到 dp [ 0 ] [ 1 ] ，但是之后就不再用到了。那么干脆把 dp [ 1 ] [ 1 ] 记到 dp [ 0 ] [ 1 ] 中，这样对于 dp [ 1 ] [ 2 ] 来说，它需要的数据就在 dp [ 0 ] [ 1 ] 和 dp [ 0 ] [ 2 ] 中。dp [ 1 ] [ 2 ] 算完后也可以同样记到 dp [ 0 ] [ 2 ] 中。

所以只需要一个长为 n+1 的一维数组就够了。

代码1：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(),n = frame[0].size();
        int dp[n + 1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0;i < m;i++)
            for(int j = 0;j < n;j++)
                dp[j + 1] = max(dp[j],dp[j + 1]) + frame[i][j];

        return dp[n];
    }
};

代码2：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int n = frame[0].size();
        int dp[n + 1];
        memset(dp, 0, sizeof(dp));
        for(auto &row : frame)
            for(int j = 0;j < n;j++)
                dp[j + 1] = max(dp[j],dp[j + 1]) + row[j];

        return dp[n];
    }
};