LeetCode2312 卖木头块

发表于 | 分类于 |
字数统计: 298 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/selling-pieces-of-wood/

周赛第四题，一眼dp不会做ToT

题意

给定一块矩阵木块，要求你把这些木块进行切割
不同的木块形状有不同的价格，问如何切割可以得到最多的钱
求最多能卖出多少钱

解法

考虑dp
令dp[i][j]表示长为i宽为j的木块能卖出的最大价格
每次枚举垂直切割的位置和水平方向切割的位置
然后每次把切割后的两块的价值和加起来取最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        vector<vector<int>> cost(m + 1, vector<int>(n + 1));
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1));
        for (auto& idx: prices) {
            cost[idx[0]][idx[1]] = idx[2];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = cost[i][j];
                for (int k = 1; k < i; k++) {
                    dp[i][j] = max(dp[i][j], dp[k][j] + dp[i - k][j]);
                }
                for (int k = 1; k < j; k++) {
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]);
                }
            }

        }
        return dp[m][n];

    }
};