title: Find number of numbers made with 1,2,3,4 such that same digits never lie together
body: <blockquote>
    <p>There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same.<br>
    Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers.<br>
    Output your answer modulo 1000000007 (10^9 + 7).</p>
  </blockquote>
  
  <p>I found this question on geeksforgeeks.com.</p>
  
  <p>The naive approach of printing all such solutions will take O(4^n). can there be a better solution using dynamic programming?</p>
  
  <p>I tried running the following code for DP. Gives the wrong answer. Can anyone suggest improvement?</p>
  
  <pre><code>#include&lt;iostream&gt;
  using namespace std;
  
  int d1[50][50][50][50],d2[50][50][50][50],d3[50][50][50][50],d4[50][50][50][50];
  
  int main(){
      int n1,n2,n3,n4;
      n1=2;n2=2;n3=1;n4=2;
      d1[1][0][0][0]=1;
      d2[0][1][0][0]=1;
      d3[0][0][1][0]=1;
      d4[0][0][0][1]=1;
      for(int i=0;i&lt;=n1;i++){
          for(int j=0;j&lt;=n2;j++){
              for(int k=0;k&lt;=n3;k++){
                  for(int l=0;l&lt;=n4;l++){
                      if(i)d1[i][j][k][l]=d2[i-1][j][k][l]+d3[i-1][j][k][l]+d4[i-1][j][k][l];
                      if(j)d2[i][j][k][l]=d1[i][j-1][k][l]+d3[i][j-1][k][l]+d4[i][j-1][k][l];
                      if(k)d3[i][j][k][l]=d2[i][j][k-1][l]+d1[i][j][k-1][l]+d4[i][j][k-1][l];
                      if(l)d4[i][j][k][l]=d2[i][j][k][l-1]+d3[i][j][k][l-1]+d1[i][j][k][l-1];
                  }
              }
          }
      }
      cout&lt;&lt;d1[n1][n2][n3][n4]+d2[n1][n2][n3][n4]+d3[n1][n2][n3][n4]+d4[n1][n2][n3][n4];
  }
  </code></pre>