【记忆化搜索】2312. 卖木头块

本文涉及知识点

记忆化搜索

LeetCode2312. 卖木头块

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

沿垂直方向按高度完全切割木块，或
沿水平方向按宽度完全切割木块
在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你不能旋转切好后木块来交换它的高度值和宽度值。

请你返回切割一块大小为 m x n 的木块后，能得到的最多钱数。

注意你可以切割木块任意次。

示例 1：

在这里插入图片描述

输入：m = 3, n = 5, prices = [[1,4,2],[2,2,7],[2,1,3]]
输出：19
解释：上图展示了一个可行的方案。包括：

2 块 2 x 2 的小木块，售出 2 * 7 = 14 元。
1 块 2 x 1 的小木块，售出 1 * 3 = 3 元。
1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 14 + 3 + 2 = 19 元。
19 元是最多能得到的钱数。
示例 2：

输入：m = 4, n = 6, prices = [[3,2,10],[1,4,2],[4,1,3]]
输出：32
解释：上图展示了一个可行的方案。包括：

3 块 3 x 2 的小木块，售出 3 * 10 = 30 元。
1 块 1 x 4 的小木块，售出 1 * 2 = 2 元。
总共售出 30 + 2 = 32 元。
32 元是最多能得到的钱数。
注意我们不能旋转 1 x 4 的木块来得到 4 x 1 的木块。

提示：

1 <= m, n <= 200
1 <= prices.length <= 2 * 10⁴
prices[i].length == 3
1 <= hi <= m
1 <= wi <= n
1 <= pricei <= 10⁶
所有 (hi, wi) 互不相同。

记忆化搜索

vW1[h][w] 表示高为h，宽为w的木块，不切割能买的价格。为0表示无法买出。
vW[h][w] 表示最大卖出价格，0表示无法卖出，-1表示未处理。
状态转移（未处理）：
垂直切：
wW[h][w] $\large Max_{x:1}^{h-1}(MS(x,w)+MS(h-x,w))$
水平切：
wW[h][w] $\large Max_{x:1}^{w-1}(MS(h,x)+MS(h,w-x))$
初始状态：vW为-1。
返回值：MS(h,w)。

代码

核心代码

template<class ELE, class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
	*seft = min(*seft, (ELE)other);
}

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}

class Solution {
public:
	long long sellingWood(int m, int n, vector<vector<int>>& prices) {
		m_vW1.assign(m + 1, vector<int>(n + 1));
		for (const auto& v : prices) {
			m_vW1[v[0]][v[1]] = v[2];
		}
		m_vW.assign(m + 1, vector<long long>(n + 1,-1));
		return MemorySeach(m, n);
	}
	long long MemorySeach(int m, int n) {
		auto& llRet = m_vW[m][n];
		if (-1 != llRet) { return llRet; }
		llRet = m_vW1[m][n];
		for (int h = 1; h < m; h++) {
			MaxSelf(&llRet, MemorySeach(h, n) + MemorySeach(m - h, n));
		}
		for (int w = 1; w < n;w++) {
			MaxSelf(&llRet, MemorySeach(m,w) + MemorySeach(m,n-w));
		}
		return llRet;
	}
	vector<vector<int>> m_vW1;
	vector<vector<long long>> m_vW;
};

VS自带的单元测试

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	int m, n;
	vector<vector<int>> prices;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			m = 3, n = 5, prices = { {1,4,2},{2,2,7},{2,1,3} };
			auto res = Solution().sellingWood(m, n, prices);
			AssertEx(19LL,res);
		}
		TEST_METHOD(TestMethod1)
		{
			m = 4, n = 6, prices = { {3,2,10},{1,4,2},{4,1,3} };
			auto res = Solution().sellingWood(m, n, prices);
			AssertEx(32LL, res);
		}
	};
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛