斐波那契数列的应用问题

Question

著名的斐波那契数列：Fn = Fn-1 + Fn-2 (F1=F2=1)，前几个斐波那契数为,1,1,2,3,5,8,13,21….
某一个整数可以拆成若干彼此不同的斐波那契数之和，比如13=13,13=5+8，13=2+3+8；16=1+2+13,16=1+2+5+8,16=3+13,16=3+5+8
现在求解这样一个问题，给定某个数值n，求有多少种方案可以把该数分解成若干彼此不同的斐波那契数之和。
求各位大神帮忙，明天就要交代码了，现在还没思路。。。可以用数组存储吗？

Answer 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 13;
            foreach (var item in Resolve(Fibonacci(n).ToArray(), new int[] { 0 }, n))
                Console.WriteLine(string.Join(" + ", item.Select(x => x.ToString())) + " = " + n.ToString());
        }

        static IEnumerable<IEnumerable<int>> Resolve(IEnumerable<int> source, IEnumerable<int> cur, int seed)
        {
            if (seed == cur.Sum()) return new List<IEnumerable<int>> { cur.Where(x => x > 0) };
            return source.Except(cur)
                .Where(x => x + cur.Sum() <= seed && x > cur.Last())
                .SelectMany(x => Resolve(source, cur.Concat(new int[] { x }), seed));
        }

        static IEnumerable<int> Fibonacci(int max)
        {
            int m = 1, n = 1;
            yield return m;
            while (n <= max)
            {
                yield return n;
                n = n + m;
                m = n - m;
            }
        }
    }
}

2 + 3 + 8 = 13
5 + 8 = 13
13 = 13
Press any key to continue . . .