已知三个int数组w,l,h，分别表示每个箱子宽、长和高，同时给定箱子的数目n。请设计算法，将箱子都堆起来（箱子不能反转），且上面箱子的宽度和长度必须小于下面的箱子。返回值为能够堆出的最高的高度。要求n小于等于500。
测试样例：
[1,1,1],[1,1,1],[1,1,1]
返回：1
[编程题]堆箱子
不同于最大上升子序列，这里随便放，不需要考虑原先的顺序。
所有箱子，首先按照w顺序排列。
接着从这个序列中找l的最大上升子序列，dp[i]表示以第i个箱子结尾的最大高度
struct sbox
{
int w=0;//width
int l=0;//length
int h=0;//high
sbox(int a, int b, int c):w(a),l(b),h(c){}
void show()
{
cout<<w<<" "<<l<<" "<<h<<endl;
}
};
bool cmp(sbox* a, sbox* b)
{
if(a->w < b->w) return true;
else return false;
}
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
if(n<=0) return 0;
vector<sbox*> allbox;
for(int i=0;i<n;i++)
{
allbox.push_back(new sbox(w[i],l[i],h[i]));
}
sort(allbox.begin(),allbox.end(),cmp);
int res=0;
int* dp = new int[n];//dp[i]表示第i个箱子的叠起来的最大值。
dp[0]=allbox[0]->h;
for(int i=1;i<n;i++)
{
int tmax=0;
for(int j=0;j<i;j++)
{
if((allbox[i]->w > allbox[j]->w) && (allbox[i]->l > allbox[j]->l))
tmax=max(tmax,dp[j]);
}
dp[i]=tmax+allbox[i]->h;
res=max(res,dp[i]);
}
return res;
}
};
发表于 2016-08-31 19:29:58
回复(0)
更多回答
# -*- coding:utf-8 -*-
class Box:
def getHeight(self, w, l, h, n):
if n <= 0:
return 0
box = [(w[i], l[i], h[i]) for i in range(n)]
box.sort(key = lambda b: (b[0], b[1]), reverse=True)
height = [0] * n
for i in range(n):
height[i] = box[i][2]
for j in range(i - 1, -1, -1):
if box[j][0] > box[i][0] and box[j][1] > box[i][1]:
height[i] = max(height[i], height[j] + box[i][2])
return max(height)
发表于 2016-08-08 07:23:59
回复(0)
Solution: 动态规划，构造一个object包括w,l,h, 然后构造一个list<object>,
并对宽度进行降序排列，然后按照长度查找最长递增子序列的方法，去计算高度h, 每次保存最大高度。
public class Box {
class SimpleBox{
int w;
int l;
int h;
public SimpleBox(int x,int y,int z){
w=x;
l=y;
h=z;
}
}
private class BoxComparator implements
Comparator<SimpleBox> {
public int compare(SimpleBox a, SimpleBox b){
return b.w-a.w;
}
}
public int getHeight(int[] w, int[] l, int[] h, int n) {
// write code here
if(w==null || l==null || h==null || n==0) return 0;
List<SimpleBox> list =new
ArrayList<SimpleBox>();
for(int i=0;i<n;i++){
SimpleBox b=new SimpleBox(w[i],l[i],h[i]);
list.add(b);
}
Collections.sort(list,new BoxComparator()); //
按宽度降序排列
int max=0;
int[] f=new int[n];
for(int i=0;i<n;i++){
f[i]=list.get(i).h;
int temp=0; // 找出前面的最大高度
for(int j=0;j<i;j++){
if(list.get(j).l>list.get(i).l){
//w宽度已经有序： 前面的宽度>后面的宽度
temp=Math.max(f[j],temp);
}
}
f[i]+=temp; // 把i叠上去后的高度
max=Math.max(max,f[i]);
}
return max;
}
}
发表于 2016-01-03 03:05:40
回复(1)
class Box {
int f[501] = {0};
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
//动态规划，转换为最长上升子序列问题
/*
1. 排序，箱子是随便摆的，但是最高的情况一定是从长/宽下到上递减
2. 如果上面的箱子长宽都小于下面的箱子那么dp[i]=dp[i-1]+max(h[i])
否则 dp[i]=h[i]
*/
//冒泡排序
for(int i = w.size()-1 ; i > 0; i--)
for(int j = w.size()-1; j > w.size()- 1 - i ; j--)
if(w[j] >= w[j-1])
{
swap(w[j],w[j-1]);
swap(l[j],l[j-1]);
swap(h[j],h[j-1]);
}
f[0] = h[0];
int maxv = f[0];
for(int i = 1; i < n; i++)
{
int fjmax = 0;
for(int j = 0; j<i; j++)
if(w[i] < w[j] && l[i] < l[j])
fjmax = max(fjmax,f[j]);
f[i] = fjmax+h[i];
maxv = max(maxv,f[i]);
}
return maxv;
}
};
发表于 2020-01-07 17:31:59
回复(0)
class Box: """ lis 用来存放以boxes[i]为底的箱子之和的最大值。 当boxes[j]的长宽<boxes[i]的长宽时（j<i），boxes[i]可以放到boxes[j]的下面。 将boxes[i]与之前的底逐一比较，求出最大值，即为lis[i]的值。 """ def getHeight(self, w, l, h, n): boxes = [(w[i], l[i], h[i]) for i in range(n)] boxes.sort() lis = [boxes[i][-1] for i in range(n)] for i in range(1, n): for j in range(i): if boxes[j][0] < boxes[i][0] and boxes[j][1] < boxes[i][1]: h = lis[j] + boxes[i][-1] if lis[i] < h: lis[i] = h return max(lis)
发表于 2019-07-22 22:09:31
回复(0)
// 还是一楼的方法好，佩服佩服， 打卡。。。。。
struct BoxTest {
int w,l,h;
};
class Box {
static bool compare(BoxTest *A, BoxTest *B) {
return A->w > B->w;
}
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
vector<BoxTest *> array;
for (int i = 0 ; i != n; i++) {
BoxTest *tmp = new BoxTest();
tmp->w = w[i];
tmp->l = l[i];
tmp->h = h[i];
array.push_back(tmp);
}
sort(array.begin(),array.end(),compare);
vector<int> f(n+1,0);
f[0] = array[0]->h;
int result = f[0];
for (int i = 1 ; i != n ; ++i) {
f[i] = array[i]->h;
int tmax = 0;
for (int j = i - 1 ; j >=0 ; --j) {
if (array[i]->w < array[j]->w && array[i]->l < array[j]->l)
tmax = max(tmax,f[j]);
}
f[i] += tmax;
result = max(f[i],result);
}
return result;
}
};
发表于 2019-01-09 14:57:00
回复(0)
整体思路：先找到最小的盘子为底座的最大高度，然后再找次最小的盘子，依次下去，便得到最大高度。
h[n]= max{ h[n]+h[i] } //h[i]可以放在h[n]盘子上。
h[n]= max{ h[n]+h[i] } //h[i]可以放在h[n]盘子上。
import java.util.*;
public class Box {
private int[] w;
private int[] l;
private int[] h;
private int[] maxH;
public int getHeight(int[] w, int[] l, int[] h, int n) {
sort(w,l,h);
this.w=w;
this.l=l;
this.h=h;
maxH=new int[n];
for(int i=0;i<n;++i){
maxH[i]=h[i];
}
int maxHeight=0;
for(int i=n-1;i>=0;--i){
int temp= calculate(i);
if(temp>maxHeight){
maxHeight=temp;
}
}
return maxHeight;
}
//计算以index为最底的箱子的最大高度，并存放在maxH的index处
public int calculate(int index){
int temp=h[index];
for(int i=index+1;i<h.length;++i){
if(putAonB(i,index)){
if(temp<h[index]+maxH[i]){
temp=h[index]+maxH[i];
}
}
}
maxH[index]=temp;
return temp;
}
//将盘子按照长度从大到小排序，若是长度相同，那么将宽度从大到小排序
public void sort(int[] w,int[] l,int[] h){
for(int i=1;i<w.length;++i){
for(int j=0;j<w.length-i;++j){
if(w[j]<w[j+1]){
swap(w,l,h,j,j+1);
}else if(w[j]==w[j+1]&&l[j]<l[j+1]){
swap(w,l,h,j,j+1);
}
}
}
}
public void swap(int[] w,int[] l,int[] h,int f, int t){
int temp=w[f];
w[f]=w[t];
w[t]=temp;
temp=h[f];
h[f]=h[t];
h[t]=temp;
temp=l[f];
l[f]=l[t];
l[t]=temp;
}
}
发表于 2017-11-26 08:53:07
回复(0)
用自己的数据结构存贮每个箱子的长宽高，然后按箱子的宽升序排序，动态规划存储每个箱子上面放若干箱子能达到的最大高度。
class Box {
struct box{
int width, length, height;
box(int w, int l, int h) :width(w), length(l), height(h){}
};
public:
int getHeight(vector<int> width, vector<int> length, vector<int> height, int n)
{
vector<box> boxes;
boxes.reserve(n);
for (int i = 0; i < n; ++i) boxes.emplace_back(width[i], length[i], height[i]);
sort(boxes.begin(), boxes.end(),
[](const box& b1, const box& b2)
{
return b1.width < b2.width || b1.width == b2.width && b1.length < b2.length;
});
vector<int> dp(n);
int maxHeight = 0;
for (int i = 0; i < n; ++i)
{
dp[i] = boxes[i].height;
for (int j = i - 1; j >= 0; --j)
{
if (boxes[j].width < boxes[i].width && boxes[j].length < boxes[i].length)
dp[i] = max(dp[i], dp[j] + boxes[i].height);
}
maxHeight = max(maxHeight, dp[i]);
}
return maxHeight;
}
};
发表于 2017-06-28 21:04:04
回复(0)
动态规划，先排序，再求最长递增子序列
class Box {
public:
static int comp(vector<int> l, vector<int> r){
return l[0]<r[0];
}
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
vector<int> res(n, 0);
vector<vector<int> > temp(n, vector<int>(3, 0));
for(int i=0; i<n; i++){
temp[i][0] = w[i];
temp[i][1] = l[i];
temp[i][2] = h[i];
}
sort(temp.begin(), temp.end(), comp);
res[0] = temp[0][2];
for(int i=1; i<n; i++){
int num = 0;
for(int j=i-1; j>=0; j--){
if(temp[i][0]>temp[j][0] && temp[i][1]>temp[j][1]){
num = max(num, res[j]);
}
}
res[i] = temp[i][2]+num;
}
int num = 0;
for(int i=0; i<n; i++){
num = max(res[i], num);
}
return num;
}
};
发表于 2017-05-27 20:07:20
回复(0)
#Python版
#最长递增子序列问题
# -*- coding:utf-8 -*-
class Box:
def getHeight(self, w, l, h, n):
if n<0:
return 0
box = [(w[i],l[i],h[i]) for i in range(n)]
box.sort(key=lambda b:(b[0],b[1]))
height = [0]*n
for i in range(n):
height[i] = box[i][2]
for j in range(i):
if box[i][0] > box[j][0] and box[i][1] > box[j][1]:
height[i] = max(height[i],height[j]+box[i][2])
return max(height)
print Box().getHeight([2768,542,832,844,2920,587,72,1724,447,809,672,2393,1235,2775,273,1165,1809,111,1263,2751,1068,2507,453,65,2338,1103,1093,2327,1995,1125,2340,1133,2123,1692,2215,140,1822,2144,2240,2916,1860,2226,698,846,2177,295],[821,2593,1581,2891,2853,1662,2747,2856,2178,865,383,523,809,998,312,237,1871,2730,823,676,568,1839,2063,1651,2704,2113,1316,2892,1874,270,1112,869,1099,1876,371,2298,2070,1514,2916,165,1043,1355,2852,1319,1979,1961],[771,2963,1599,1910,2317,2884,872,2463,949,341,2718,1500,1071,539,2463,1355,104,2989,1240,240,981,0,2172,3011,621,681,1178,2518,2766,615,460,2399,2443,2894,799,1726,2454,2099,2279,2911,2018,426,2896,224,2663,351],46)
编辑于 2016-12-13 11:50:36
回复(0)
public int getHeight(int[] w, int[] l, int[] h, int n) {
dp = new int[n];
for (int i = 0; i < n; i++) {
int t = f(i, w, l, h, n);
sum = sum < t ? t : sum;
}
return sum;
}
int sum, dp[];
int f(int k, int[] w, int[] l, int[] h, int n) { //第k个箱子能装最多的高度
if (dp[k] != 0) {
return dp[k];
}
int max = h[k];
for (int i = 0; i < n; i++) {
if (w[i] < w[k] && l[i] < l[k]) {
int t = f(i, w, l, h, n);
if (t + h[k] > max) {
max = t + h[k];
}
}
}
return dp[k] = max;
}
发表于 2016-09-10 21:28:06
回复(0)
private void swap(int[] w, int i, int j) {
int temp = w[i];
w[i] = w[j];
w[j] = temp;
}
private void sort(int[] w, int[] l, int[] h) {
for (int i = 0; i < w.length; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (w[j] < w[j + 1]) {
swap(w, j + 1, j);
swap(l, j + 1, j);
swap(h, j + 1, j);
} else
break;
}
}
}
public int getHeight(int[] w, int[] l, int[] h, int n) {
// write code here
sort(w, l, h);
int[] dp = new int[n];
int result = Integer.MIN_VALUE;
for (int i = 0; i < n; ++i) {
int maxh = h[i];
for (int j = 0; j < i; ++j) {
if (l[j] > l[i]) {
int t = dp[j] + h[i];
if (t > maxh) {
maxh = t;
}
}
}
dp[i] = maxh;
if (result < maxh)
result = maxh;
}
return result;
}
发表于 2016-04-16 00:08:12
回复(0)
本题是一个利用动态规划求最大严格上升子序列的问题，由于要满足 底盘长宽的限制， 因此只需要找到满足
长与宽闲置的一个最大上升子序列即可，然后求出最大高度。
进行计算前，需要对初始数组进行排序(即三个传入参数)，按单关键字排序即可,即宽度或高度。
其中f[n]表示前 n个箱子可以堆的最大高度。
class Box {
int f[501] = {0}; //存放n个箱子的最大上升高度
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
for(int i = w.size()-1 ; i > 0; i--){
for(int j = w.size()-1; j > w.size()- 1 - i ; j--){
if(w[j] >= w[j-1]/*&& l[j] >= l[j-1]*/){
swap(w[j],w[j-1]);
swap(l[j],l[j-1]);
swap(h[j],h[j-1]);
}
}
}
for(int i = 0; i < w.size(); i++){
cout<<w[i]<<" "<<l[i]<<" "<<h[i]<<endl;
}
f[0] = h[0];
int maxv = f[0];
for(int i = 1; i < n; i++){
f[i] = h[i];
int tmax = 0;
for(int j = i-1; j >= 0; j--){
if(w[i] < w[j] && l[i] < l[j]){
tmax = max(tmax,f[j]);
}
}
f[i] += (tmax);
maxv = max(maxv,f[i]);
}
return maxv;
}
};
发表于 2015-08-24 00:22:12
回复(6)
//经典的有向无环图模型的DP问题
//选择某个起点使之有向无环图的最大路径长度
import java.util.*;
public class Box {
public int getHeight(int[] w, int[] l, int[] h, int n) {
boolean[][] graph = new boolean[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(w[i]>w[j]&&l[i]>l[j])//使底部的箱子长宽大于上面的，若有箱子长宽小，则有到其的有向边
graph[i][j] = true;
}
}
int[] dp = new int[n];
int ans = 0;
for(int i=0;i<n;i++){//选择起点
int tmp = dfs(i,graph,h,dp);
ans = Math.max(ans,tmp);
}
return ans;
}
public int dfs(int bottom,boolean[][] graph,int[] h,int[] dp){
if(dp[bottom]>0) return dp[bottom];
int n = graph.length;
int top = 0;
for(int i=0;i<n;i++){
if(graph[bottom][i])
top=Math.max(top,dfs(i,graph,h,dp));
}
return dp[bottom] = top+h[bottom];//缓存当前结点的最大路径长度
}
}
发表于 2017-09-07 16:01:35
回复(1)
public int getHeight(int[] w, int[] l, int[] h, int n) {
// write code here
/*
* 按照宽度从大到小排序，定maxH[i]为从0开始到放入第i-1个箱子（第i-1个一定被放入），满足长宽条件的最大高度
* 从第1个开始为h[0]，初始maxH[i] = h[i]，tmax记录放入第i-1个箱子时可达到的最大高度
* 伪码如下：
* maxH[0] = h[0];
* res = maxH[0];
* for i = 1:n
* maxH[i] = h[i];
* tmax = 0;
* for j = i-1 : 0
* if l[j] > l[i] && w[j] > w[i]//看能放下当前i箱子的情况下，选择高度最大的那种
* tmax = max(tmax, maxH[j]);
* maxH[i] += tmax;
* res = max(res, maxH[i]);//res仅存到放入第i-1个箱子为止，出现过的高度最大值
* end for;
* return res;
*/
if(n <= 0){
return 0;
}
//sort
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(w[i] < w[j]){
swap(w, i, j);
swap(l, i, j);
swap(h, i, j);
}
}
}
//get height
int[] maxH = new int[n];
maxH[0] = h[0];
int res = maxH[0];
for(int i = 1; i < n; i++){
maxH[i] = h[i];
int tmax = 0;
for(int j = i-1; j >=0; j--){
if(w[j] > w[i] && l[j] > l[i]){
tmax = (tmax > maxH[j])? tmax : maxH[j];
}
}
maxH[i] += tmax;
res = res > maxH[i] ? res : maxH[i];
}
return res;
}
private void swap(int[] mat, int x, int y) {
// TODO Auto-generated method stub
int tmp = mat[x];
mat[x] = mat[y];
mat[y] = tmp;
}
编辑于 2016-06-04 22:18:19
回复(1)
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
for(int i=n-1;i>0;i--)
for(int j=n-1;j>n-i-1;j--)
if(w[j-1]<w[j]){
swap(w[j-1],w[j]);
swap(l[j-1],l[j]);
swap(h[j-1],h[j]); } int dp[503]; memset(dp,0,sizeof(dp)); dp[0] = h[0]; int Max= dp[0],t; for(int i=1;i<n;i++){ dp[i] = h[i]; t = 0; for(int j=i-1;j>=0;j--) if(w[i]<w[j] && l[i]<l[j]) t = max(t,dp[j]); dp[i] += t; Max = max(Max,dp[i]); } return Max;
}
};
发表于 2019-03-05 11:57:39
回复(0)
# -*- coding:utf-8 -*- class Box: def getHeight(self, w, l, h, n): boxes = [] for i in range(n): boxes.append([w[i], l[i], h[i]]) boxes.sort(key=lambda x: x[0]) # print(boxes) dp = [0] * len(boxes) for i in range(n): dp[i] = boxes[i][2] for j in range(i): if boxes[j][1] < boxes[i][1] and boxes[j][0] < boxes[i][0]: dp[i] = max(dp[i], dp[j] + boxes[i][2]) # print(dp) return max(dp)
运行时间：179ms
占用内存：5728k
发表于 2018-12-19 12:07:40
回复(0)
//严格的最大递增子序列问题
//先按照宽度排序（或者长度排序），然后从第一个点开始找起，看看本身能达到的最大高度;
//参考代码如下;
class Box {
public:
//交换数值；
void swap(int& a,int& b)
{
int temp=a;
a=b;
b=temp;
}
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
//step1:按照宽度排列(冒泡排序法)；
for(int i=0;i<w.size()-1;i++)
{
for(int j=i+1;j<w.size();j++)
{
if(w[j]>w[i])
{
swap(w[i],w[j]);
swap(l[i],l[j]);
swap(h[i],h[j]);
}
}
}
int maxH[200] = {0}; //存放n个箱子的最大上升高度；
maxH[0]=h[0];//第一个箱子得到的最大高度就是本身；
int res=maxH[0];
for(int i=1;i<n;i++)
{
maxH[i]=h[i];//该箱子的最小高度（至少）就是本身的高度；
int temp=0;
//下面这个for循环主要计算该点（前面）能够得到的最大高度；
for(int j=i-1;j>=0;j--)
{
if(w[j]>w[i] && l[j]>l[i])
{
temp=(temp>maxH[j])?temp:maxH[j];
}
}
//将本身的高度加上之前箱子可以得到的最大高度，得到现在的高度；
maxH[i]+=temp;
//该res主要不断维护最大值，不然还要在maxH数组中寻找最大值；
res=(res>maxH[i])?res:maxH[i];
}
return res;
}
};
编辑于 2016-08-18 21:36:15
回复(4)
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
// 整体思路是，首先对n个箱子按照宽度或长度降序排列，这样可以保证高度最大的序列一定是这个序列的子序列（想一想为什么）。
// dp[i]表示的是在0~i号箱子组成的序列中，以i号箱子为顶的最大高度。
// 外层循环遍历0~n-1号箱子，求以每个箱子为顶的最大高度dp[i]，最大的dp[i]即为答案。
// 内层循环对每个i，遍历前面0~i-1，找到i号箱子能够堆在其上的最高高度prev_max，那么dp[i]就等于i号箱子的高度加上prev_max。
// 选择排序
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (w[i] < w[j]) {
swap(w[i], w[j]);
swap(l[i], l[j]);
swap(h[i], h[j]);
}
}
}
// dp[i]表示的是在0~i号箱子组成的序列中，以i号箱子为顶的最大高度。
vector<int> dp(n);
dp[0] = h[0];
int maxh = dp[0];
for (int i = 1; i < n; ++i) {
dp[i] = h[i]; // dp[i]至少是i号箱子的高度
int prev_max = 0;
for (int j = i - 1; j >= 0; --j) {
if (w[i] < w[j] && l[i] < l[j]) { // 判断i号箱子能否堆在其上
prev_max = max(prev_max, dp[j]);
}
}
dp[i] += prev_max;
maxh = max(maxh, dp[i]);
}
return maxh;
}
};
发表于 2022-08-29 21:14:41
回复(0)
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// sort the box by weight
sortBox(w, l, h, n);
memset(dp, 0, sizeof(dp) );
dp[0] = h[0];
int maxHeight = dp[0];
for (int i = 1; i < n; ++i) {
dp[i] = h[i];
for (int j = 0; j < i; ++j) {
if(w[i] < w[j] && l[i] < l[j]) {
if (dp[j] + h[i] > dp[i]) {
dp[i] = dp[j] + h[i];
}
}
}
if (dp[i] > maxHeight) {
maxHeight = dp[i];
}
}
return maxHeight;
}
private:
void swapBox(int &a, int &b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
void sortBox(vector<int> &w, vector<int> &l, vector<int> &h, int n) {
for (int i = 0; i < n; ++i) {
bool flag = false;
for (int j = 0; j < n-i-1; ++j) {
if (w[j] <= w[j+1]) {
swapBox(w[j], w[j+1]);
swapBox(l[j], l[j+1]);
swapBox(h[j], h[j+1]);
flag = true;
}
}
if (!flag) {
break;
}
}
}
int dp[503] = {0};
};
发表于 2020-07-21 15:25:43
回复(0)
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
//按照宽度降序,冒泡排序
for(int i=0;i<n;++i)
for(int j=0;j<n-i-1;j++)
{
if(w[j]<w[j+1])
{
swap(w[j+1],w[j]);
swap(l[j+1],l[j]);
swap(h[j+1],h[j]);
}
}
vector<int>dp(n,0);
int max_height=0;
for(int i=0;i<n;++i)
{
dp[i]=h[i];
int height=h[i];
for(int j=0;j<i;++j)
{
if(w[j]>w[i]&&l[j]>l[i])
dp[i]=max(dp[j]+height,dp[i]);
}
max_height=max(max_height,dp[i]);
}
return max_height;
}
};
//这道题应用了求最大上升子序列的问题，和最大上升子序列不同的是，最大子序列的序列元素的相对位置是固定的，而堆箱子问题的序列元素的
//相对位置是可变的，要想求出堆箱子的最大高度，就要尽量使宽度和长度按照降序排列，因为两者不能同时排列，所以只能先按照一个排列，
//然后选择另一个满足条件的，上面的代码中使用了冒泡排序的方法
//dp数组中，dp[i]表示的是以第i个箱子为顶点（第i个箱子必须被选到）的可堆积的最大高度
发表于 2020-07-08 16:40:23
回复(0)
问题信息
难度：
42条回答
100收藏
21342浏览
通过挑战的用户
查看代码-
2023-03-03 19:54:50
-
2023-03-03 19:49:09
-
2022-09-30 19:58:54 -
2022-09-30 11:43:20 -
2022-09-22 17:33:25
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
