动态规划之"可作为Fibonacci数列前缀的非空子序

问题定义：
给定一个序列{a_n}, 求可作为fibonacci数列的非空子序列个数。 最后结果 mod 1,000,000,007!
输入
One line with an integer n.
Second line with n integers, indicating the sequence {an}.
For 30% of the data, n<=10.
For 60% of the data, n<=1000.
For 100% of the data, n<=1000000, 0<=ai<=100000.

fibonacci 数列：
F₁ = 1, F₂ = 1
Fn = Fn-1 + Fn-2, n>=3

样例输入
2 1 1 2 2 3
样例输出
7

解题思路

为区分样例中的每个元素， 假设重写样例为 2₁ 1₂ 1₃ 2₄ 2₅ 3₆. 下标代表其在序列中索引号.
部分fibonacci数列： 1, 1, 2, 3, 5, 8, .....
上述例子中，符合条件的子序列:
{1₂},
{1₃},
{1₂ 1₃},
{1₂ 1₃ 2₄},
{1₂ 1₃ 2₅},
{1₂ 1₃ 2₅ 3₆},
{1₂ 1₃ 2₄ 3₆}

首先明白子序列的含义: 子序列是指从原序列中任意选定一些项，保持其相对顺序不变，得到的序列为原序列的子序列。
也就是说，对于当前枚举的原序列第i项，可以和原序列第1~i-1项中任意一个子序列构成一个新的子序列。
本题中要求构成的序列必须满足斐波拉契数列的前缀，所以在第1到第i-1项中符合要求的子序列一定满足下面这个条件：
假设原序列中第1到第i-1项的某个子序列{s₁ ,..., s_m}是Fibonacci数列的前缀, 该子序列和原序列第i项构成新的新子序列如果是Fibonacci子序列，那么a[i], s_m必须是Fibonacci数列的相邻项。

因此，不用考虑原序列中的非Fibonacci数。
此外，还需要标记出原序列中每一个留下来的项对应于斐波拉契数列的第几项

动态规划思想：
令 f(i,j) 表示原数列中前i个数中，以Fibonacci 数列中第 j项 (从下标1开始) 作为子序列结尾元素的子序列个数.

假设枚举到原序列的第 i 项，a[i] 是Fibonacci序列的第 j 项 （a[i]>1）, 则
边界条件：f(i, 0)=1, f(i, j)=0; i 取 {0, 1, 2, ..., n}中的值；j 取 {1, 2, ..., n}中的值
递推公式：f(i, j) = f(i-1, j-1) + f(i-1, j)

原序列前 i 项中，以Fibonacci序列第j项作为结尾元素的子序列的构成方式:

1. 当原序列的第i个元素 a[i] 在其前的元素里没有出现过时： 原序列的第 i 项，与原序列中前 i-1 个元素以Fibonacci序列的第 j-1 项构成的子序列结合，因此 有 f(i-1, j-1)个是Fibonacci前缀新子序列。
2. 当原序列的第i个元素 a[i] 在其前的元素里出现过时：假设在原序列前 i-1 个元素中，出现过和 a[i] 相等的元素 a[i']，其中 i' < i. 由于a[i]是Fibonacci序列的第 j 项，a[i']也是Fibonacci序列的第 j 项，因此 f(i-1, j) 也表示原序列前 i 个元素以a[i]作为结束元素的符合要求的子序列的个数。如果在前i-1个元素中不存在和当前元素a[i]相等的元素，该项为0.

Fibonnaci数列中前两项具有相同值，因此需要特殊处理。
a[i] == 1时：
f(i, 1) = f(i-1, 1)
f(i, 2) = f(i-1, 2) + f(i-1, 1)

假设序列的长度为n, 则 可作为Fibonacci数列前缀的非空子序列个数: f(n,1)+...+f(n,K) , K 是最大fabonacci数在fabonacci数列中的下标 (从1开始)。【按照题目要求，记得 在计算过程中要记得MOD 100,000,007】

题目中给定原序列中数字最大为100,000，假设斐波拉契数列中小于等于100,000的有K项, (可提前计算出K=25)
则该递推公式的时间复杂度为O(KN)

时空优化方案

在上面的递推公式中，我们可以发现在转移过程中，f(i, j)中大部分数都是直接继承的f(i-1, j)。同时f(i, . )只会在枚举到第 i 项的时候更新，只会在计算第i+1项时用到。
因此，我们可以只使用一维数组存储解 f(j).

在更新f(j)时，需要注意: 当 a[i]==1时，
要先更新作为斐波拉契数列第2项的1，再计算作为斐波拉契数列第1项的1。
这是因为f(1)更新后会影响到f(2)的计算，而反过来不会。

优化后，时间复杂度：O(n), 空间复杂度：O(n)

代码如下

// 优化后的算法
```java
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static final int Max=1000010;
    static int[] fibs=new int[Max];
    static Map<Integer,Integer> indFibs = new HashMap<>();
    static void init(){
        fibs[0]=fibs[1]=1;
        for(int i=2; ; ++i){
            fibs[i]=fibs[i-2]+fibs[i-1];
            indFibs.put(fibs[i], i+1);// 记录fib数在序列中的位置
            if(fibs[i]>=Max)
                break;
        }
        indFibs.put(1, 2);
    }
    static void display(int[] f){
        for(int i=0; i<f.length; ++i){
            System.out.print(f[i] +" ");
        }
        System.out.println();
    }
    static void solver(){
        init();
        int[] f = new int[26];
        f[0]=1;
        final int M = 1000000007;
        Scanner scan = new Scanner(new BufferedInputStream(System.in));
        int n = scan.nextInt();
        for(int i=0; i<n; ++i){
            int x = scan.nextInt(); 
            if(indFibs.containsKey(x)){
                int j = indFibs.get(x);
                f[j] = (f[j-1]+f[j]) % M;
                if(x==1){
                    f[1]=(f[1]+f[0]) % M;
                }
            }
        }
        scan.close();
        int ans = 0;
        for(int i=1; i<=25; ++i){
            ans = (ans+f[i])%M;
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        solver();
    }
}

题目来源:hihoCoder