暗黑的字符串

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            if(n==1){
                System.out.println(3);
                continue;
            }
            long[] dp_same = new long[n+1];
            long[] dp_diff = new long[n+1];
            dp_same[2]=3;
            dp_diff[2]=6;
            for(int i=3;i<=n;i++){
                dp_same[i]=dp_same[i-1]+dp_diff[i-1];
                dp_diff[i]=2*dp_same[i-1]+dp_diff[i-1];
            }
            System.out.println(dp_same[n]+dp_diff[n]);
        }
        
    }
}

是否是暗黑字符串只受前两个字符的影响，如果前两个字符相同，那么第三个字符就有三种可能，如果前两个字符不相同，那么第三个字符就只有两种可能。
n=2时，重复字符串个数为R=3，不重复的为F=6
每一个字符串在下一次都会生成一个重复的字符串所以Rn=Rn-1+Fn-1,
每个重复字符串会生成两个非重复字符串，一个非重复字符串只会生成一个非重复字符串，所以Fn = Fn-1+2*Rn-1

最终结果为Rn+Fn

private static int getCount(int num){
        if(num == 1)
            return 3;
        int r = 3, nr = 6;
        for(int i=2;i<num;i++){
            int newR = r+nr;
            int newNR = r*2+nr;
            r = newR;
            nr = newNR;
        }
        return r+nr;
    }

/**
 f(n):长度为n的字符串含有的暗黑字符串个数
 S(n):长度为n的字符串含有的暗黑字符串个数，但约束条件为末尾两个字符相同
 D(n):长度为n的字符串含有的暗黑字符串个数，但约束条件为末尾两个字符不同
 很容易得到：f(n) = 3*S(n-1) + 2*D(n)

 f(n) = 3*S(n-1) + 2*D(n)
 f(n-1) = S(n-1) + D(n-1)
 由以上两式可以推出：f(n) = 2*f(n-1) + S(n-1)
 
 f(n-1) = S(n-1) + D(n-1)
 S(n) = S(n-1) + D(n-1)
 由以上两式可以推出：f(n-1) = S(n)

 f(n) = 2*f(n-1) + S(n-1)
 f(n-1) = S(n)
 由以上两式可以推出：f(n) = 2*f(n-1) + f(n-2)
 
 最终地递推公式为：
 f(1) = 3
 f(2) = 9
 f(n) = 2*f(n-1) + f(n-2), n >= 3
 
 */

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int count = in.nextInt();
            long num1 = 3, num2 = 9;
            long res = 0;
            if (count == 1) System.out.println(num1);
            else if (count == 2) System.out.println(num2);
            else {
                for (int i = 3; i <= count; i++) {
                    res = 2 * num2 + num1;
                    num1 = num2;
                    num2 = res;
                }
                System.out.println(res);
            }
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            System.out.println(dp(n));
        }
    }
    
    public static long dp(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 3;
        dp[2] = 9;
        for (int i = 3; i <= n; i++) {
            dp[i] = 2 * dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}