当前位置:网站首页>leetcode2312. 卖木头块(困难,周赛)
leetcode2312. 卖木头块(困难,周赛)
2022-07-02 01:51:00 【重you小垃】
思路:dp
如何想到dp的?
垂直/水平切割,得到更小的子问题
先垂直再水平和先水平再垂直会得到同样大小的两块木块,因此1:存在重复子问题
对于同样高和宽的两个木块所获得的最多钱数和得到这两个木块的过程无关,因此2:无后效性
获得两块小木块的最多钱数,就获得了大木块的最多钱数,因此3:最优子结构
满足以上三个条件,因此->dp
状态转移:
p[m][n]表示高m宽n的木块能获得的最大钱数
dp[m][n]能直接卖的话获得一个price
dp[m][n]=max(dp[m][j]+dp[m][n-j]),1<=j<=n-1
dp[m][n]=max(dp[j][n]+dp[m-j][n]),1<=j<=m-1
递归终止:dp[1][1]
代码实现方式?由于会遍历到所有的状态,因此用递推实现
class Solution {
public:
long long sellingWood(int m, int n, vector<vector<int>>& prices) {
vector<vector<long long>> dp(m + 1, vector<long long>(n + 1)); //long long
auto p = dp;
for (auto& a : prices) p[a[0]][a[1]] = a[2];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = p[i][j];
for (int k = 1; k <= j - 1; ++k) dp[i][j] = max(dp[i][j], dp[i][k] + dp[i][j - k]);
for (int k = 1; k <= i - 1; ++k) dp[i][j] = max(dp[i][j], dp[k][j] + dp[i-k][j]);
}
}
return dp[m][n];
}
};
边栏推荐
- TSINGSEE青犀平台如何实现同一节点同时播放多个视频?
- Five skills of adding audio codec to embedded system
- Design and implementation of radio energy transmission system
- 1217 supermarket coin processor
- SAP ui5 beginner tutorial 20 - explanation of expression binding usage of SAP ui5
- 479. Additive binary tree (interval DP on the tree)
- JMeter (II) - install the custom thread groups plug-in
- What is AQS and its principle
- 如何用一款产品推动「品牌的惊险一跃」?
- II Basic structure of radio energy transmission system
猜你喜欢
【LeetCode 43】236. The nearest common ancestor of binary tree
The smart Park "ZhongGuanCun No.1" subverts your understanding of the park
机器学习基本概念
[rust web rokcet Series 2] connect the database and add, delete, modify and check curd
成功实现边缘编码需要了解的六大经验教训
Learn C language from scratch day 025 (maze)
Basic concepts of machine learning
微信小程序中使用tabBar
This is the report that leaders like! Learn dynamic visual charts, promotion and salary increase are indispensable
基于SSM实现微博系统
随机推荐
Should enterprises choose server free computing?
Using mongodb in laravel
Makefile simple induction
电子协会 C语言 1级 32、计算2的幂
new和malloc的区别
C language 3-7 daffodils (enhanced version)
Quatre stratégies de base pour migrer la charge de travail de l'informatique en nuage
Learn basic K-line diagram knowledge in three minutes
Five skills of adding audio codec to embedded system
Exclusive delivery of secret script move disassembly (the first time)
Selection of field types for creating tables in MySQL database
电子协会 C语言 1级 33 、奇偶数判断
【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享
6-2 vulnerability exploitation - inevitable problems of FTP
SAP ui5 beginner tutorial 20 - explanation of expression binding usage of SAP ui5
JMeter (I) - download, installation and plug-in management
Discussion on the idea of platform construction
MySQL如何解决delete大量数据后空间不释放的问题
It's already 30. Can you learn programming from scratch?
"C language programming", 4th Edition, edited by he Qinming and Yan Hui, after class exercise answers Chapter 3 branch structure