計算具有相同的前半部分和後半部分總和的偶數長度二進制序列  


難度級別 中烘焙
經常問 24 * 7創新實驗室 亞馬遜 戴爾 GE醫療集團
動態編程

問題“用前一半和後一半相同的和計算偶數長度的二進制序列”指出給您一個整數。 現在找出構建大小為2 * n的二進制序列的方法,以使上半部分和下半部分具有相同數量的設置位。

計算具有相同的前半部分和後半部分總和的偶數長度二進制序列

例  

2
6

解釋

二進制序列是0000、1001、1010、0110、0101、1111。因此總數為1。

途徑  

天真的方法

解決問題的一種方法是使用遞歸。 因此,我們將跟踪需要在兩半中設置的位數。 因此,該解是三態解。 狀態是需要在前半部分中設置的位數,要在後半部分中設置的位數,所遍歷的位數。 通用的遞歸解決方案看起來像下面的代碼所示。

#include <bits/stdc++.h>
using namespace std;

int n;
int rec(int a, int b, int i){
    if(i == n)
        if(a == 0 && b == 0)
            return 1;
        else
            return 0;
    return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>n;
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans += rec(i, i, 0);
        cout<<ans;
    }
}

該解決方案很好,但是效率很低。 從而提高了時間複雜度。 我們可以用 動態編程。 但是由於這三個狀態,時間複雜度仍然是O(N ^ 3)。

也可以看看
查找是否有一個總和為0的子數組

更好的方法

更好的方法是考慮更改遞歸公式和使用 動態編程 解決問題。 而不是保留要在上半部分和下半部分中設置的位數的計數。 我們可以利用這種差異將兩種狀態簡化為一個狀態。 現在,我們的遞歸公式已更改,因此我們的時間複雜度和空間複雜度也發生了變化。 我們可以編寫一個可以在O(N ^ 2)時間內運行的解決方案。

C ++代碼以相同的前半部分和後半部分總和來計算偶數長度的二進制序列

#include <bits/stdc++.h>
using namespace std;

int n;
int rec(int diff, int i, vector<vector<int>> &dp){
    if(i == n)
        if(diff == 0)
            return 1;
        else
            return 0;
    if(dp[diff+n][i] != -1)
        return dp[diff+n][i];
    return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}

int main(){
    cin>>n;
    vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
    int ans = rec(0, 0, dp);
    cout<<ans;
}
6
924

Java代碼以相同的前半部分和後半部分總和來計數偶數長度的二進制序列

import java.util.*;

class Main{
  static int n;
  static int rec(int diff, int i, int dp[][]){
      if(i == n)
          if(diff == 0)
              return 1;
          else
              return 0;
      if(dp[diff+n][i] != -1)
          return dp[diff+n][i];
      return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      int dp[][] = new int[2*n+2][n+1];
      for(int i=0;i<2*n+2;i++){
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = -1;
      }
      int ans = rec(0, 0, dp);
      System.out.print(ans);
  }
}
6
924

複雜度分析

時間複雜度

O(N ^ 2), 因為問題中存在N ^ 2個不同的狀態。 因此,時間複雜度是多項式。

空間複雜度

O(N ^ 2), 因為我們已經創建了2D DP陣列。 因此,空間複雜度也是多項式。

也可以看看
最大大小子數組總和等於k

最佳方法

最佳方法是使用二項式係數來計算問題的答案。 我們可以認為這兩個部分是獨立的。 然後,如果它們是獨立的,我們只需要設置一些位即可。 考慮我們需要在n位中設置k位。 因此,我們可以簡單地寫出等於nCk * nCk的方法數量。 因此,如果我們計算k等於0到k等於n的值。 我們會找到答案的。

C ++代碼以相同的前半部分和後半部分總和來計算偶數長度的二進制序列

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int C = 1, answer = 1;
    for (int i = 1; i<=n ; i++)
    {
        C = (C * (n+1-i))/i;
        answer += (C*C);
    }
    cout<<answer;
}
6
924

Java代碼以相同的前半部分和後半部分總和來計數偶數長度的二進制序列

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int answer = 1, C = 1;
      for(int i = 1; i<=n; i++)
      {
          C = (C * (n+1-i))/i;
          answer += (C*C);
      }
      System.out.print(answer);
  }
}
6
924

複雜度分析

時間複雜度

上), 因為我們已經運行了一個循環直到N。因此該算法具有線性時間複雜度。

空間複雜度

O(1),因為空間複雜度是恆定的。