pe-0755

dp.设f(k,s)表示选择斐波那契前k项,所有元素和小于等于s的情况数.转移方程是

$$f(k,s)=\begin{cases} 0&s<0\\ 1&k=0\\ 2^k&\sum_{i=1}^k F_i\le N\\ f(k-1,s)+f(k-1,s-F_k)&other \end{cases}$$

假如范围内所有斐波那契数列都小于s,那么随便选,否则排除边界状况之后,新的斐波那契数字可以选也可以不选,答案直接转移即可.