POJ 2229 Sumsets

蟻本章末問題

問題概要

リンク

• ある数字Nが与えられる
• Nを2の累乗の数の和で表す
• 例えば4なら
  • 4
  • 2 + 2
  • 2 + 1 + 1
  • 1 + 1 + 1 + 1
• そのような組み合わせは何通りか

解法

• dp[i] := N=iの時の組み合わせの数
• dp[i] = dp[i/2] + dp[i-1] then i mod 2=0
  dp[i] = dp[i-1] other