問題描述
小易有n塊磚塊倡蝙，每一塊磚塊有一個(gè)高度。小易希望利用這些磚塊堆砌兩座相同高度的塔。為了讓問題簡(jiǎn)單冬阳，磚塊堆砌就是簡(jiǎn)單的高度相加蛤虐，某一塊磚只能使用在一座塔中一次。小易現(xiàn)在讓能夠堆砌出來的兩座塔的高度盡量高肝陪，小易能否完成呢驳庭。
輸入描述
輸入包括兩行：
第一行為整數(shù)n(1 ≤ n ≤ 50)，即一共有n塊磚塊
第二行為n個(gè)整數(shù)氯窍，表示每一塊磚塊的高度height[i] (1 ≤ height[i] ≤ 500000)
輸出描述
如果小易能堆砌出兩座高度相同的塔饲常，輸出最高能拼湊的高度，如果不能則輸出-1.
保證答案不大于500000狼讨。
輸入例子
3
2 3 5
輸出例子
5
分析
很容易聯(lián)想到01背包問題贝淤。如果兩座塔的高度都等于所有磚塊總高度sum的一半，那么兩座塔的高度最高政供。但是很遺憾播聪，不是每個(gè)磚塊都會(huì)被用到，所以01背包沒法解決這個(gè)問題布隔。
繼續(xù)延續(xù)動(dòng)態(tài)規(guī)劃的思路离陶。加上兩座塔分別被命名為A和B。我們建立一個(gè)狀態(tài)表dp[i][j]：i={0,1}衅檀，表示上下狀態(tài)行招刨，用來壓縮狀態(tài)空間；j為兩座塔的高度差B-A哀军，我們會(huì)始終保證這個(gè)值為非負(fù)數(shù)沉眶，所以需要把j整體偏移sum打却，即[-sum,sum]+sum-->[0,2*sum]；dp[i][j]為狀態(tài)行i下沦寂，高度差B-A=j時(shí)学密，B的最大高度。
1. Base
dp[0][sum] = 0传藏，即當(dāng)沒有放磚塊腻暮，并且B-A為sum-sum=0（考慮之前的偏移）時(shí)，B的最大高度為0
2. Transition Function
dp[i][j]=max(dp[!i][j], dp[!i][j - h], dp[!i][j + h] + h)
dp[!i][j]表示不放該磚塊毯侦；
dp[!i][j - h]表示把磚塊放到A塔上哭靖；
dp[!i][j + h] + h表示把磚塊放到B塔上。
3. result
dp[i][sum]
note
動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程有時(shí)候真的很難找
