Can somebody tell me how to approach these problems?.. Both are based on same concept with same strategy but based on DP. So please if u have a strong concept based on DP then share with us…

Thank you!

For problem 1

Start with an exponential recursive solution and add memoisation afterwards .

For example , you can define F(i,j,k) as number of strings of length i with continuous sequence of B’s of length j and max length of all continous subarrays of B’s is k . For example if the string you built uptil now is ABBABBBABB your state would be (11,2,3) . Transitions are pretty obvious : You can append an ‘A’ and go to F(i+1,0,k) or append a B and go to F(i+1,j+1,max(k,j+1)). This is obviously a naive way O(N^3) and can also be done in O(N) .

Problem 2 is very similar and can be done in O(N*K)

Your approach is good but you could not tell us how to think in O(N) time with O(N) extra space! As i found a very good and direct solution of this one! but still don’t know the strategy of this one!

#include<bits/stdc++.h>

using namespace std;

int main()

{

long long int n,k;

```
scanf("%lld %lld",&n,&k);
```

long long a[n+5],i;

```
for(i=0;i<=k-1;i++)
a[i]=0;
a[k]=1;
for(i=k+1;i<=n;i++)
a[i]=2*a[i-1]+(1<<(i-k-1))-a[i-k-1];
long long ans1=a[n];
long long ans2=(1<<n);
long long g=__gcd(ans1,ans2);
ans1=ans1/g;
ans2=ans2/g;
printf("%lld/%lld\n",ans1,ans2);
return 0;
```

}