leetcode 600 Count number of binary strings without consecutive 1 不出现连续1二进制数量

ゝ一世哀愁。 2022-06-02 20:53 274阅读 0赞

Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.

Examples:

Input: N = 2
Output: 3
// The 3 strings are 00, 01, 10

Input: N = 3
Output: 5
// The 5 strings are 000, 001, 010, 100, 101

思路是用DP，考虑从n位增加一位到n+1位的情况。如果首位是0，那么第n+1位的首位既可以是0，也可以是1，因为都不会产生连续的1；如果首位是1，那么只能生成首位是0的n+1位数，才能避免出现连续的1。
用zeros记录首

代码如下：

  1. // C++ program to count all distinct binary strings
  2. // without two consecutive 1's
  3. #include <iostream>
  4. using namespace std;
  6. int countStrings(const int n)
  7. {
  8.     vector<int> a(n), b(n);
  9.     a[0] = b[0] = 1;
  10.     for (int i = 1; i < n; i++)
  11.     {
  12.         a[i] = a[i - 1] + b[i - 1];
  13.         b[i] = a[i - 1];
  14.     }
  15.     return a[n - 1] + b[n - 1];
  16. }
  19. // Driver program to test above functions
  20. int main()
  21. {
  22.     cout << countStrings(3) << endl;
  23.     return 0;
  24. }

发表评论

表情：
评论列表 （有 0 条评论，274人围观）

还没有评论，来说两句吧...

相关阅读