问题：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];}
};