二の累乗の問

最近他のアルゴリズム問題を見ながら混乱しました。二進コードのすべての件を数えて余分な物を引く方法でいけなかった。他の探索空間が必要だそうです。トップコーダーの解説を見れば動的計画法の答えが可能です。でもまた最初に見て考えられない正解です。再帰の入力変数は累計の二進桁と以下の桁から足す残高です。データー構成はDP[k][b]です。Xの列は2^iと入力列に存在する件数の関係を示す。reccountの再帰関数が一つな（ｋ、ｂ）組で多くて二回呼ばれる。ｋの上限が６０とｂの上限も六十で複雑性がO(2*60*60)=O(7200)です。
The basic intuition for the "PowersOfTwo" problem is as follows. say there are three twos in the set to be considered. You can affect the sum in two ways: place a one in the 2^1's bit and carry 2/2 = 1 2's to the higher bits or place a 0 in the 2^1's bit and carry 3/2=1 2's to the higher bits. The key insight is that all sums comprised of terms that are all powers of two can be represented as a binary string. If the maximal size of the input vector is 50 and the maximal element value is 2^50, the maximal sum length is 50*2^50<60 bits. The number of possible binary strings expressing all sums can be written as a recurrence relation, and the results of subproblems can be cached in memory and reused. Thus, for an extreme case where the input is {1,2,4,...,2^50}, only 2*50=100 recursive calls are needed. 出力累計が漸化式に書かれるから部分的な答えを覚えて算出のコストが減る。