【算法挨揍日记】day20——LCR 166. 珠宝的最高价值、931. 下降路径最小和

雨点打透心脏的1/2处 2024-02-20 10:44 56阅读 0赞

###  ###

## LCR 166. 珠宝的最高价值 ##

[LCR 166. 珠宝的最高价值][LCR 166.]

### 题目描述： ###

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

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

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

![4279b99562674803a1b7bb7122fe22bc.png][]

### 解题思路： ###

> 状态表示： dp\[i\]\[j\]表示到达（i，j）后的最大价值
> 
> 状态转移方程：dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i\]\[j-1\])+frame\[i-1\]\[j-1\]
> 
> 初始化：dp\[i\]\[0\]和dp\[0\]\[i\]（这里的i是从0到len1和len2）都为0
> 
> 填表顺序：左到右
> 
> 返回值：dp\[len1\]\[len2\]

### 解题代码： ###

class Solution {
    public:
        int jewelleryValue(vector<vector<int>>& frame) {
            int len1=frame.size();
            int len2=frame[0].size();
            vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));
            for(int i=1;i<=len1;i++)
            {
                for(int j=1;j<=len2;j++)
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
            }
            return dp[len1][len2];
        }
    };

--------------------

## 931. 下降路径最小和 ##

[931. 下降路径最小和][931.]

### 题目描述： ###

给你一个 `n x n` 的 **方形** 整数数组 `matrix` ，请你找出并返回通过 `matrix` 的**下降路径**的**最小和** 。

**下降路径** 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 `(row, col)` 的下一个元素应当是 `(row + 1, col - 1)`、`(row + 1, col)` 或者 `(row + 1, col + 1)` 。

![095a9698ca854ee184aeff46a1263316.png][]

![8f20c8821c7c479cb97e2aa4ce01b717.png][]

### 解题思路： ###

> 状态表示：dp【i】【j】表示为到（i，j）位置后的最小和
> 
> 状态转移方程：
> 
> dp\[i\]\[j\]=min(min(dp\[i-1\]\[j-1\],dp\[i-1\]\[j\]),dp\[i-1\]\[j+1\])+matrix\[i-1\]\[j-1\];
> 
> 初始化：我们需要将初始化一个len+1\*len+2的数组，其中第一行为0，其他为INT\_MAX
> 
> 填表顺序：左到右
> 
> 返回值：最后一行最小值

### 解题代码： ###

class Solution {
    public:
        int minFallingPathSum(vector<vector<int>>& matrix) {
            int len=matrix.size();
            vector<vector<int>>dp(len+1,vector<int>(len+2,INT_MAX));
            for(int i=0;i<len+2;i++)dp[0][i]=0;
            for(int i=1;i<=len;i++)
            {
                for(int j=1;j<=len;j++)
                {
                    dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1])+matrix[i-1][j-1];
                }
            }
            int ret=INT_MAX;
            for(int i=1;i<=len;i++)
            ret=min(ret,dp[len][i]);
            return ret;;
        }
    };

###  ###

[LCR 166.]: https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/
[4279b99562674803a1b7bb7122fe22bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/1588ed764c95466da579f6f02033d42b.png
[931.]: https://leetcode.cn/problems/minimum-falling-path-sum/
[095a9698ca854ee184aeff46a1263316.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/57a0ef8fdcc848fc9cbfff3fd629ea9c.png
[8f20c8821c7c479cb97e2aa4ce01b717.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/cfb76c1c81d84842933413b1b7494da2.png