Given a positive integer , return the number of non-negative integers whose binary representation does not contain consecutive ones. For (binary ): valid numbers are (binary ). Invalid: (binary ).
Answer: . This is digit DP on binary representation. Instead of base , you work in base . Before reading the solution, try to identify the base case and recursive relationship yourself.