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


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!


using namespace std;

int main()
long long int n,k;

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

long long a[n+5],i;






long long ans1=a[n];

long long ans2=(1<<n);

long long g=__gcd(ans1,ans2);




return 0;


1 Like