动态规划

状态计算 :
f[i]={cuboids[i][2]if 不存在kmax(f[k])+cuboids[i][2]if k∈[1,i−1]f[i] = \begin{cases} cuboids[i][2] &\text{if } 不存在k \\ max(f[k])+cuboids[i][2] &\text{if } k \in [1,i-1] \end{cases}f[i]={cuboids[i][2]max(f[k])+cuboids[i][2]​if 不存在kif k∈[1,i−1]​

其中 cuboids[i][2]cuboids[i][2]cuboids[i][2] 表示 iii 的高度。

设长方体 AAA 的宽长高为 w1,l1,h1w_1,l_1,h_1w1​,l1​,h1​ ，BBB 的宽长高为 w2,l2,h2w_2,l_2,h_2w2​,l2​,h2​
解题需要的性质 : 若 w1≤l1≤h1,w2≤l2≤h2w_1\le l_1 \le h_1,w_2\le l_2 \le h_2w1​≤l1​≤h1​,w2​≤l2​≤h2​ ，要 AAA 可以堆叠在 BBB 上，当且仅当 w1≤w2w_1\le w_2w1​≤w2​ 且 l1≤l2l_1\le l_2l1​≤l2​ 且 h1≤h2h_1\le h_2h1​≤h2​ 。
证明 :
①满足 w1≤w2w_1\le w_2w1​≤w2​ 且 l1≤l2l_1\le l_2l1​≤l2​ 且 h1≤h2h_1\le h_2h1​≤h2​ ，一定是符合题意的堆叠方案。
②要证明仅当，可以反证，假设当 w1>w2w_1>w_2w1​>w2​ 或 l1>l2l_1>l_2l1​>l2​ 或 h1>h2h_1>h_2h1​>h2​ ，AAA 可以堆在 BBB 上，

1. 当 w1>w2w_1>w_2w1​>w2​ ，
   有 w2 仅当 l1≥l2l_1\ge l_2l1​≥l2​ 且 h1≥h2h_1\ge h_2h1​≥h2​ ，可以堆叠(包含在原命题)，(w1>w2w_1>w_2w1​>w2​ 且 l1≥l2l_1\ge l_2l1​≥l2​ 且 h1≥h2h_1\ge h_2h1​≥h2​）
   其他情况不可堆叠。
2. 当 l1>l2l_1>l_2l1​>l2​ ，
   因为 w1≤l1≤h1w_1\le l_1\le h_1w1​≤l1​≤h1​ , w2≤l2≤h2w_2\le l_2\le h_2w2​≤l2​≤h2​ ，
   有w2≤l2 则 w2w_2w2​ 和 l2l_2l2​ 只能与 w1w_1w1​ 匹配，
   但 w1w_1w1​ 只可匹配其中之一，
   不可以堆叠。
3. 当 h1>h2h_1>h_2h1​>h2​ ，
   有 w2≤l2≤h2 仅当 w1≥w2w_1\ge w_2w1​≥w2​ 且 l1≥l2l_1\ge l_2l1​≥l2​ ，可以堆叠(包含在原命题)
   其他情况不可堆叠。

综上，只有原命题成立，反证的结论才能成立，否则反证不成立。所以原命题成立。

class Solution {
public:int maxHeight(vector>& cuboids) {for(auto &c:cuboids) sort(c.begin(),c.end());sort(cuboids.begin(),cuboids.end());int n = cuboids.size();vector f(n,0);int ans = 0;for(int i = 0;if[i] = cuboids[i][2];for(int j = 0;j=cuboids[j][1]&&cuboids[i][2]>=cuboids[j][2])f[i] = max(f[i],f[j]+cuboids[i][2]);ans = max(ans,f[i]);}return ans;}
};

1. 时间复杂度 : O(n2)O(n^2)O(n2) ， nnn 是长方体的数量，状态数量是 nnn ，转移数量是 nnn ，状态转移的时间复杂度 O(n2)O(n^2)O(n2) 。
2. 空间复杂度 : O(n)O(n)O(n) ，所有状态的空间复杂度 O(n)O(n)O(n) 。

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。