600. 不含连续1的非负整数 动态规划

600. 不含连续1的非负整数

给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。

示例 1:

输入: n = 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

示例 2:

输入: n = 1
输出: 2

示例 3:

输入: n = 2
输出: 3

提示:

• 1 <= n <= 1e9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功。其实准确的说是没想出来，今天想出了

方法：动态规划

 数位dp看几个关键点：上限，前导0/验重，dp二维影响因子，状态转移。本题用二进制，干脆把数值转成二进制字符数组。

1.上限：有上限，是给定数值，前面达到上限的情况受到上限影响

2. 前导0/验重：不用管，不需要验重复，也就不需要记录是否前导0

3. 二维影响因子：题目给定是不能出现连续1，因此二维影响因子就是末尾元素，末尾为0和1的，后续选择策略不同

4. 状态转移：0一定可以填，1在受到上限影响且上限为1时不能填，1在末尾为1的情况也不能填，因为题目要求不能有连续1

class Solution {
      int[][] dp;
      char[] cs;
    public int findIntegers(int n) {
        cs = Integer.toBinaryString(n).toCharArray();
        dp = new int[cs.length][2];
        for(int i = 0; i < cs.length; i++){
            dp[i][0]=dp[i][1]=-1;
        }
        return dfs(0,true,0);
    }
 
    private int dfs(int index, boolean isLimit, int end){
        if(index == cs.length) return 1;
        if(!isLimit&&dp[index][end]!=-1) return dp[index][end];
        int ans = dfs(index+1,isLimit&&cs[index]=='0',0);
        if((!isLimit||cs[index]=='1')&&end!=1) ans += dfs(index+1,isLimit,1);
        if(!isLimit) dp[index][end]=ans;
        return ans;
    }
 
}