矩形覆盖 

消失的硬盘容量

双子积木塔

<pre><code>&#x27;&#x27;&#x27; 遍历H数组，每个积木可以选择放在高的塔上，也可以选择放在矮的塔上，也可以不放在任何塔上 用一个集合记录已经遍历过的数组可能出现的两个塔的高度，把所有高度的结果都保存 &#x27;&#x27;&#x27; sum_H = sum(H) s = {(0, 0)} # 元组(diff, lower_height)记录两个积木塔的高度差，以及较矮的积木塔高度 tmp = set() ans = 0 for h in H: for diff, lower in s: if diff == h: ans = max(ans, lower + h) if lower + diff + h &lt;= sum_H // 2: tmp.add((diff + h, lower)) if lower + h &lt;= sum_H // 2: tmp.add((abs(h - diff), lower + min(diff, h))) s = s.union(tmp) tmp = set() print(ans if ans else &#x27;FAIL&#x27;)</code></pre>

发现示例64那个也是错的，你们的代码怎么会有解。。。。

楼主这代码，代入这个H = [14, 7, 14, 4, 3, 5]，结果是21，应该是fail

不太稳定，时而通过时而不通过。

<pre style="font-family: Consolas; font-size: 12pt;"><pre style="font-family: Consolas; font-size: 12pt;">dp = [[],[],[],[],[]] # dp[i][j] = x 其中i代表前i个数中，j代表高塔和低塔的高度差，x代表高塔的高度，最后答案为dp[n][0]

for i in range(5):
 for j in range(500000 + 10):
 dp[i].append(-1)#初始化数组

dp[0][0] = 0# dp[0][0]意思是还没开始选择数之前的状态，因为还没开始选择数字，故高度差低塔高度为0

nowp = set() #用于保存这个循环需要处理的数据的j值
nxtp = set() #用于保存下个循环需要处理的数据的j值

nxtp.add(0)#dp[0][0]被修改了，所以其j值0被加入下次需要处理的数据

for i in range(len(H)): #对于第i块
 nowp = nxtp.copy()
 nxtp.clear()
 now = i%5
 nxt = now + 1
 if now == 4:
 nxt = 0
 for j in nowp: # 每次保存被修改的数据
 if dp[now][j] != -1:
 if dp[now][j]&gt;dp[nxt][j]: #情况1：不选择它
 dp[nxt][j] = dp[now][j]
 nxtp.add(j)
 if j &gt;= H[i]: #情况2：选择它放在低塔上，还是比高塔低
 if dp[now][j] + H[i]&gt;dp[nxt][j-H[i]]:
 dp[nxt][j-H[i]] = dp[now][j] + H[i]
 nxtp.add(j - H[i])
 else: #情况3：选择它放在低塔上，但放了之后就比高塔高了，高塔变成低塔
 if dp[now][j] + j &gt; dp[nxt][H[i]-j]:
 dp[nxt][H[i]-j] = dp[now][j] + j
 nxtp.add(H[i]-j)
 if dp[now][j] &gt; dp[now][j+H[i]]: #情况4：选择它放在高塔上，高塔还是高
 dp[nxt][j+H[i]] = dp[now][j]
 nxtp.add(j+H[i])


if dp[(len(H))%5][0] == 0 or dp[(len(H))%5][0] == -1:
 print &quot;FAIL&quot;
else:
 print dp[(len(H))%5][0]</pre></pre>

发现示例也是错的，H = [15, 15, 14, 24, 14, 3, 20, 23, 15]，应该无解

楼主这个也不对呀，示例H = [15, 15, 14, 24, 14, 3, 20, 23, 15,]加多一个1，64变72了. 比如：H = [15, 15, 14, 24, 14, 3, 20, 23, 15, 1]，输出72

动态规划 + 滚动数组 + 集合的AC代码

# 原理就是我们以第一个数为基础，后面每个数都有加或不加的可能，算出所有可能的值的大小，值等于一半积木高度和sum(H)/2即可 # 1.建一个数组triangle，放入第一个数H[0] # 2.triangle里增加一个H[i] # 3.对H[i]前的数，都加一次一次H[i],再新增到triangle里形成新数组 # 4.直到找到这triangle里有相当于sum(H)/2的数即可 h = int(sum(H) / 2) # 一半高度和，sum(H)不超过500000，所以后面有h &gt; 250000这个判断 if sum(H) % 2 != 0 or max(H) &gt; 500000 or h &gt; 250000: # 直接先判断有没有可能有解，题目示例很明显有问题 print(&quot;FAIL&quot;) else: H.sort() # 为了好看，排个序 triangle = [H[0]] # 随便建一个数组 for i in range(1, len(H)): # print(triangle) #查看每次循环的增量 triangle.append(H[i]) k = len(triangle) for j in range(0, k - 1): triangle.append(triangle[j] + H[i]) if h in triangle: print(h) break elif i == len(H)-1: print(&quot;FAIL&quot;)

自己验证正确，题目示例和几个评论的都有问题

这个是不是题目出错了。第三个示例明明是个奇数应该做不到才对。

H = [7, 4, 3, 1]，这个代进去就错了

<pre style="font-family: Consolas; font-size: 12pt;">dp = [[],[],[],[],[]]
#dp[i][j] i = 前i个 j = 高低塔高度差为j dp[i][j] = 低塔高度 时间复杂度 = O（500000 * len（H））
for i in range(5):
 for j in range(500000 + 10):
 dp[i].append(-1)

dp[0][0] = 0


for i in range(len(H)):
 now = i%5
 nxt = now + 1
 if now == 4:
 nxt = 0
 for j in range(500000):
 dp[nxt][j] = -1
 for j in range(500000):
 if dp[now][j] != -1:
 dp[nxt][j] = max(dp[nxt][j],dp[now][j])
 if j &gt;= H[i]:
 dp[nxt][j-H[i]] = max(dp[nxt][j-H[i]],dp[now][j] + H[i])
 else:
 dp[nxt][H[i]-j] = max(dp[nxt][H[i]-j],dp[now][j] + j)
 dp[nxt][j+H[i]] = max(dp[now][j+H[i]],dp[now][j])

if dp[(len(H))%5][0] == 0 or dp[(len(H))%5][0] == -1:
 print &quot;FAIL&quot;
else:
 print dp[(len(H))%5][0]
</pre>

第156题：双子积木塔

输出字典key

时间就是金钱

取石子游戏

计算表达式