大意: 给定数$n$, 求将$n$划分为最少的斐波那契数的和或差.
每次取相邻$n$的斐波那契数一定最优, 考虑证明.
结论1:存在一个最优解,使得每个斐波那契数使用不超过1次.(考虑$2F_n=F_{n-2}+F_{n+1}$)
结论2:存在一个最优解,使得同号数不相邻, 异号数间隔$ge 2$.
根据结论1和2, 假设最优解所选最大斐波那契数为$F_k$, 那么
$n$的下界为$F_k-F_{k-3}-F_{k-5}-...$, $k$为奇时为$F_{k-1}$, $k$为偶时为$F_{k-1}+1$
$n$的上界为$F_k+F_{k-2}+F_{k-4}+...$, $k$为奇时为$F_{k+1}-1$, $k$为偶时为$F_{k+1}$
所以我们每次考虑解的最大数, 一定为与$n$相邻的斐波那契数.