题目链接: hdu5686 ( Problem B )

\(dp[n][1]\) 代表长度为 \(n\) 的全 \(1\) 序列构成的新序列中以 \(1\) 为尾的序列数量；

\(dp[n][0]\) 代表长度为 \(n\) 的全 \(1\) 序列构成的新序列中以 \(2\) 为尾的序列数量。

递推关系如下：

\[\begin{cases} dp[i][0]=dp[i-1][1],&i>0 \\ dp[i][1] = dp[i-1][0]+dp[i-1][1], & i>0 \\ dp[0][0]=1, dp[0][1]=0 \end{cases} \]

由于 \(dp[n]\) 的状态只与 \(dp[n-1]\) 的状态有关，故可只用一维数组迭代 \(n\) 次。

结果可能很大，超过 \(2^{200}\) ，可用 \(java\) 的 \(BigInteger\) 。

\(java\ AC\) 代码:

/**
 * hdu5686 Problem B
 *
 */

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            // dp[1]代表以1为尾的序列数量，dp[0]代表以2为尾的序列数量
            BigInteger[] dp = {BigInteger.ONE, BigInteger.ZERO};
            while (n-- != 0) {
                BigInteger t0 = dp[1];
                BigInteger t1 = dp[0].add(dp[1]);
                dp[0] = t0;
                dp[1] = t1;
            }
            System.out.println(dp[0].add(dp[1]));
        }
    }
}

事实上，答案为斐波那契数列的第 \(N+1\) 项。