Google算法题：不包含连续1的非负整数

　

非负数

题目

题目来源：Link

分析

每一步的选择都依赖前一步的选择，是前面选择的组合，子问题重合，所以用动态规划

代码

package com.graph;

import java.util.*;

public class Solution {
	
	public int solve(int n){
		if(n==0) return 1;
		String binary = integer.toBinaryString(n);
		int len=binary.length();
		int[] f = new int[len+1];
		f[0]=1;
		f[1]=2;
		//计算场i的二进制位符合要求的个数
		for(int i=2; i<=len; i++) {
			f[i] = f[i-1]+f[i-2];
		}
		//计算0~n的符合要求的总个数
		int sum=0;
		for(int i=0, k=len; i<len; i++,k--) {
			if(binary.charAt(i)=='1') {
				sum+=f[k-1];	
				if(i>0 && binary.charAt(i-1)=='1') {
					return sum;
				}
			}						
		}
		//先前没有return，到这里，说明n本身没有算进去
		sum++;
		
		return sum;
	}
	public static void main(String[] args) {
		Solution s = new Solution();
		System.out.println(s.solve(9));
	}
}

相关阅读

原来连续两次递归调用很简单

void rec(int N) { //为了区分这两个递归，分别为它们取个别名好了 if (N>0){  rec(N - 1);//rec1 rec(N - 10)

连续霸榜第一的“学习强国”，到底是一款什么样的神仙Ap

图片来源图虫：已授站长之家使用声明：本文来自于微信公众号 三节课(ID：sanjieke01)，作者：范米索，授权站长之家转载发布。如果你最近看过A

excel页码怎么设置页码不连续

多时候，我们在制作Word文档，尤其是制作报告、论文、书籍等复杂文档的时候，需要对目录、前言、正文分别设置页码，也就是我们常说的设置

连续霸榜第一的“学习强国”，到底是一款什么样的神仙Ap

免费看剧上课朋友们，你以为“学习强国”只是满屏的党政宣传带有浓厚政治气息的内容吗??那你真要错过一堆宝藏功能了。(没事，我本来

Excel表格怎样用IMPOWER函数计算整数幂

IMPOWER函数使计算复数的整数幂的函数，那如何在EXCEL表格中使用该函数呢?不懂的朋友会请多多学习哦，下面就跟seo实验室小编一起来学