堆砖块
问题描述
小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)
输出描述
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。
输入例子
3
2 3 5
输出例子
5
分析
很容易联想到01背包问题。如果两座塔的高度都等于所有砖块总高度sum的一半，那么两座塔的高度最高。但是很遗憾，不是每个砖块都会被用到，所以01背包没法解决这个问题。
继续延续动态规划的思路。加上两座塔分别被命名为A和B。我们建立一个状态表dp[i][j]：i={0,1}，表示上下状态行，用来压缩状态空间；j为两座塔的高度差B-A，我们会始终保证这个值为非负数，所以需要把j整体偏移sum，即[-sum,sum]+sum-->[0,2*sum]；dp[i][j]为状态行i下，高度差B-A=j时，B的最大高度。
1. Base
dp[0][sum] = 0，即当没有放砖块，并且B-A为sum-sum=0（考虑之前的偏移）时，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
动态规划的状态转移方程有时候真的很难找
