寻找多种生成数字的方法 [英] Find a Number of ways to Generate a Number

问题描述

我只给出了斐波那契数字，我必须找出使用 K 仅斐波那契数字。

I have given Fibonacci digits only , i have to find out the numbers of ways to generate a number using K Fibonacci numbers only.

约束：

1<=K<=10
1<=N<=10^9

例如：

N=14 and K=3

有两种方法：

(8,5,1) and (8,3,3) 

这是我的递归解决方案：

Here is my recursive solution:

public static void num_gen(int i ,long val ,int used){

      if(used==0){

          if(val==n) ans++;
          return ;
      }

      if(i==Fib.length) return ;

      for(int j=0;j<=used;j++){

          long x = j*Fib[i];
          if(x+val<=n){
              num_gen(i+1,x+val, used-j);
          }
      }

}

此解决方案对于N较大且K = 10的值将超时。您能为我提供更好的算法吗？

This solution will timeout for large value of N and K=10. Can you provide me algorithm with better complexity.

推荐答案

这可以表示为多项式，其中指数是斐波那契数。

This can be expressed as multiplying polynomials where exponents are Fibonacci numbers.

因数为K。

结果是指数为N的结果多项式成员的系数。

The result is a coefficient of the member of the result polynomial whose exponent equals N.

示例：
由3个数字组成7的方法是什么，其中3个数字中的每个数字可以是1,2或3。 p>

Example: What is the number of ways to compose number 7 from 3 numbers where each of these 3 numbers can be 1,2 or 3.

（x +x²+x³）³=x⁹+3x⁸+6x⁷+7x⁶+6x⁵+3x⁴+x³

(x + x² + x³)³ = x⁹ + 3x⁸ +6x⁷ + 7x⁶ + 6x⁵ + 3x⁴ + x³

结果为6，因为它是结果多项式的x the成员的系数。

Result is 6 since it is the coefficient of the x⁷ member of the result polynomial.

这篇关于寻找多种生成数字的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！