第三题其实和信封嵌套问题类似。 n个箱子,每个箱子存三种情况放入一个数组(长度3*n),三个长宽高,保证长度大于等于宽度, 然后排序,长度以升序排序,长度相同时以宽度降序排序。 遍历数组,每个位置i的左边所有宽度小于i位置宽度的箱子一定是可以叠放在i箱子的。 遍历的时候更新dp数组,dp[i]初始化为i位置箱子高度,遍历左侧,dp[i] = max(dp[i],dp[左侧位置] +i位置的箱子高度),然后dp数组最大值就是答案。
点赞 3

相关推荐

牛客网
牛客企业服务