当前位置:网站首页>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];
}
};
边栏推荐
- The difference between new and malloc
- Four basic strategies for migrating cloud computing workloads
- Memorabilia of domestic database in June 2022
- PR second training
- Volume compression, decompression
- I Brief introduction of radio energy transmission technology
- 734. Energy stone (greed, backpack)
- How to use a product to promote "brand thrill"?
- 卷積神經網絡(包含代碼與相應圖解)
- Three core problems of concurrent programming
猜你喜欢
Pyldavis installation and use | attributeerror: module 'pyldavis' has no attribute' gensim '| visual results are exported as separate web pages
Introduction to ffmpeg Lib
[技术发展-21]:网络与通信技术的应用与发展快速概览-1- 互联网网络技术
[Floyd] post disaster reconstruction
matlab 实现语音信号重采样和归一化,并播放比对效果
matlab 使用 audioread 、 sound 读取和播放 wav 文件
1222. Password dropping (interval DP, bracket matching)
It's already 30. Can you learn programming from scratch?
This is the form of the K-line diagram (pithy formula)
Android: how can golden nine and silver ten squeeze into the first-line big factories from small and medium-sized enterprises? The depth of interview questions in large factories
随机推荐
Implementation of Weibo system based on SSM
TSINGSEE青犀平台如何实现同一节点同时播放多个视频?
Makefile simple induction
1217 supermarket coin processor
5g/4g pole gateway_ Smart pole gateway
Ubuntu20.04 PostgreSQL 14 installation configuration record
【视频】马尔可夫链原理可视化解释与R语言区制转换MRS实例|数据分享
How to debug apps remotely and online?
"C language programming", 4th Edition, edited by he Qinming and Yan Hui, after class exercise answers Chapter 3 branch structure Exercise 3
Fastadmin controls the length of fields in the table
Laravel artisan common commands
There are spaces in the for loop variable in the shell -- IFS variable
Openssl3.0 learning XXI provider encoder
Is the knowledge of University useless and outdated?
MPLS experiment operation
Android high frequency network interview topic must know and be able to compare Android development environment
自动浏览拼多多商品
How to use a product to promote "brand thrill"?
479. Additive binary tree (interval DP on the tree)
[Maya] the error of importing Maya into Metahuman