凡度网络北京网站建设公司,在家做私房菜的网站,seo文章优化技巧,网站开发工具的功能有哪些文章目录1. 题目2. 解题1. 题目
你正在安装一个广告牌#xff0c;并希望它高度最大。 这块广告牌将有两个钢制支架#xff0c;两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。 举个例子#xff0c;如果钢筋的长度为 1、2 和 3#xff0c;则…
文章目录1. 题目2. 解题1. 题目
你正在安装一个广告牌并希望它高度最大。 这块广告牌将有两个钢制支架两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。 举个例子如果钢筋的长度为 1、2 和 3则可以将它们焊接在一起形成长度为 6 的支架。
返回广告牌的最大可能安装高度。如果没法安装广告牌请返回 0。
示例 1
输入[1,2,3,6]
输出6
解释我们有两个不相交的子集 {1,2,3} 和 {6}它们具有相同的和 sum 6。示例 2
输入[1,2,3,4,5,6]
输出10
解释我们有两个不相交的子集 {2,3,5} 和 {4,6}它们具有相同的和 sum 10。示例 3
输入[1,2]
输出0
解释没法安装广告牌所以返回 0。提示
0 rods.length 20
1 rods[i] 1000
钢筋的长度总和最多为 5000来源力扣LeetCode 链接https://leetcode-cn.com/problems/tallest-billboard 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][j] 表示处理完 i 钢筋两边差距为 j 时可以组成的最大高度
class Solution {
public:int tallestBillboard(vectorint rods) {if(rods.size() 1)return 0;int dp[20][5001], n rods.size();int total accumulate(rods.begin(), rods.end(), 0);// dp[i][j] 表示处理完 i 支架两边差距为 j 时可以组成的最大高度memset(dp, -1, sizeof(dp));dp[0][rods[0]] dp[0][0] 0;for(int i 1; i rods.size(); i) { //样本维度for(int j 0; j total; j){if(dp[i-1][j] -1)//上一行状态不存在continue;// 当前钢筋不要丢弃dp[i][j] max(dp[i][j], dp[i-1][j]);// 当前钢筋加在长的一边dp[i][jrods[i]] max(dp[i][jrods[i]], dp[i-1][j]);// 当前钢筋加在短的一边现在高度差为 abs(j-rods[i])dp[i][abs(j-rods[i])] max(dp[i][abs(j-rods[i])], dp[i-1][j]min(j, rods[i]));}}// 返回高度差为 0 的情况return dp[n-1][0]-1 ? 0 : dp[n-1][0];}
};40 ms 8.1 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
