Hint:16=3+13=3+5+8=1+2+13=1+2+5+8
对于 30% 的数据,n<=256
对于 100% 的数据,n<=10^18
直接记忆化搜索就行了,fibo(88) 就已经 >=10^18.
设 g(x,y) 为考虑前 x 个斐波那契数的和为 y 的方案数.
答案即为 g(87,n).
转移的时候可以剪枝:
1. 当 y<=f[x] 的时候可以转移到 g(x-1,y-f[x).
2. 当 y
解释一下第二个,因为斐波那契数列有注明前缀和公式 f(1)+f(2)+...+f(x)=f(x+2)-1 (证明可以考虑分
奇偶添补),所以当 y>=f[x+1] 的时候,g(x-1,y) 一定是 0 了,不用再转移了.
来源: http://www.bubuko.com/infodetail-2457713.html