【回溯-数字全排列&&dfs&&动态规划】CD129 0左边必有1的二进制字符串的数量

描述

给定一个整数n，求由“0”字符和“1”字符组成的长度为n的所有字符串中，满足“0”字符的左边必有“1”字符的字符串的数量。

输入描述：

输入一行，包含一个整数n（1≤n≤2∗107）（1≤n≤2∗107）。

输出描述：

输出一个整数，表示返回的答案，由于字符串的数量巨大，可能会溢出，请输出对229229取模后的答案。

示例1

输入：

1

输出：

1

说明：

只有“1”满足

示例2

输入：

2

输出：

2

说明：

只有“10”和“11”满足

示例3

输入：

3

输出：

3

说明：

只有“101”，“110”，“111”满足

备注：

时间复杂度O（log2n）O（log2​n）。额外空间复杂度O（1）O（1）。

如果没有限制0左边必须有1则全排列的数字一共有 Math.pow(2,n)个。

由于限制0左边必须有1，所以在 第 i 位选择数字0的时候，需要比较上1个数字是否是1，否则不能选择数字0。所以有代码：

   public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        System.out.println(dfs(0,n,0));
    }

    public static int dfs(int i,int n,int last) {
        if(i==n) {
            return 1;
        }
        int count = 0;
        for(int d=0;d<=1;d++){
            if(d==0 && last==0) continue;  //选择数字d=0的时候有条件限制
            count+=dfs(i+1,n,d);
        }
        return count;
    }

以上问题如果使用dfs在n很大的时候会超时，毕竟时间复杂度是2的n次方。所以当n很大的时候可以考虑动态规划。

n=1，只有1满足。 dp[1]=1

n=2，只有10，11满足 dp[2]=2

n=3, 在n=1的时候左边增加 10即可获取，也可以在n=2的时候左边增加1 得到。所以dp递推公式：

dp[n]=dp[n-1] + dp[n-2] //变成斐波那契的排列了。

     static class Main {

        public static final int MOD = 1 << 29;

        public static void main(String[] args) {
            int n = new Scanner(System.in).nextInt();
            System.out.println(getCount(n));
        }

        public static int getCount(int n) {
            if (n <= 2) {
                return n;
            }
            int a = 1, b = 2; // f(1) = 1, f(2) = 2

            for (int i = 3; i <= n; i++) {
                int tmp = (a + b) % MOD;
                a = b;
                b = tmp;
            }
            return b;
        }
    }