Dynamic programming problem! Easy question.

Problem 1,
Problem 2

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! :slight_smile:

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) .

Spoiler

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

2 Likes

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;

}

1 Like