个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
【C++】? ??
??????http://t.csdnimg.cn/6AbpV
数据结构与算法
前言:这个专栏主要讲述动态规划算法,所以下面题目主要也是这些算法做的 ?
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
题目链接:珠宝的最高价值
题目
现有一个记作二维矩阵?frame
?的珠宝架,其中?frame[i][j]
?为该位置珠宝的价值。拿取珠宝的规则为:
注意:珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝,比如?frame = [[0]]
。
示例 1:
输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
提示:
0 < frame.length <= 200
0 < frame[0].length <= 200
frame
?的珠宝架,其中?frame[i][j]
?为该位置珠宝的价值。输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
我们这题使用动态规划,我们做这类题目可以分为以下五个步骤
时间复杂度:O(mn)。
空间复杂度:O(mn) 或?O(n),即为动态规划需要使用的空间。
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame)
{
int m = frame.size(), n = frame[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
}
}
return dp[m][n];
}
};