Dynamic programming

help
1

can anyone explain the logic for this question.

2

you have to give the output of no of strings that are possible of length n and are
lexicographically sorted.
( lexicographically sorted :- abcd is lexicographically sorted beacuase a comes before b and b comes before c but bcda is not because a comes before b )

1 Like
3

bro i know that … i want the logic to solve the question (lexicographically ka matlab pata h mujhe).

1 Like
4

Let us assume that in the final solution x_i represents the number of occurrences of the vowel i in your final solution. Now since the problem statement asks for the total number of lexicographically sorted sequences so it’s a very obvious observation that any valid solution will look like
aaa...eeee...iiii...oooo....uuuu
Hence only thing that matters is the number of occurrences of each character in the valid solution
So answer will just be the number of integral solutions of the following equation
x_a+x_e+x_i+x_o+x_u=N
which is a well known stars and bars formula , \binom{N+5-1}{5-1}= \binom{N+4}{4}

AC_CODE 
class Solution {
public:
  long long dp[56][56] ;
  int countVowelStrings(int n) {
    for(int i=0;i<=55;i++)
      for(int j=0;j<=i;j++){
        if(j==0 || i==j)
          dp[i][j]=1  ;
        else
          dp[i][j]=dp[i-1][j-1]+dp[i-1][j] ;
      }
    return dp[n+4][4] ;
  }
};
1 Like
5

Try forming a recursive relation, keep this in mind:

  1. for any i, the vowels in string [i+1; n] should only be greater than or equal to ith vowel (this is enough for the string to be lexicographically sorted)
6

Here’s the relation:
f(i, j) -> ans for string of length i with previous largest vowel being jth vowel
f(i, j) = f(i-1, j) + f(i-1, j+1)… f(i-1, 5) # fixing first vowel as either jth or j+1th… or 5th vowel

7

My Noob friendly solution Hope it helps :smiley:

int countVowelStrings(int n) {
      int arr[n+1][6];
      /*
      arr[i][1]=ending with 'a',arr[i][2]=ending with 'e'....
      
      */
      for(int i=0;i<=n;i++)
          for(int j=0;j<=5;j++)
              arr[i][j]=0;
      
      for(int i=1;i<=5;i++)
          arr[1][i]=1;
      
      
      for(int i=2;i<=n;i++){
          for(int j=1;j<=5;j++){
              for(int k=1;k<=j;k++){
                  arr[i][j]+=arr[i-1][k];
              }
          }
      }
      int res=0;
      for(int i=1;i<=5;i++)
          res+=arr[n][i];
      return res;
  }