Tile Stack Problem

general
, , , ,
1

Tile_Stack_problem

I was trying to solve the following problem mentioned and i have come up with a memoization technique this much but I run into memory overflow error how can i reduce the memory

This is what I have done

#include<bits/stdc++.h>

using namespace std;

int dp[301][1001][281];

#define mod 1000000007

int count(int n , int m, int k ,int start , int num,int stack)

{
/// start is the present symbol on top of stack , num is the number of times the symbol is present till now and stack is the size of the stack

if(start>m)
return 0;

if(num>k)return 0;

if(stack==n)return 1;
if(dp[stack][start][num]!=-1)
	return dp[stack][start][num];
dp[stack][start][num] = ((count(n,m,k,start,num+1,stack+1)+count(n,m,k,start+1,0,stack)))%mod;
return dp[stack][start][num]%mod;

}
int main()
{

for(int i=0;i<=300;i++)

	for(int j=0;j<=1000;j++)

		for(int k=0;k<=280;k++)

		dp[i][j][k] =-1;
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
int ans = count(n,m,k,1,0,0);
cout<<ans;

}

Could any one provide a recursive solution that uses less memory…

2

Hey @athulpai

You can have a look at this recursive solution. But its a brute force solution. While going with the recursive approach, we go to each and every possible permutation and thus it is bound to give a TLE. This solution passes 4 test cases on Hackerrank and gives TLE for the rest of them.

Your memoization approach is the correct way to go but with a little improvement.
int dp[301][1001][281]; This is the reason for you getting a memory overflow. You can solve it by using an extra space sum array. Instead of 1 3D matrix you can have 2 2D matrix and then try to solve the problem. This will solve your memory overflow problem. It will be better if you try to solve the problem by yourself first and if you still need some help you can see this link. This is the accepted solution on Hackerrank using memoization technique.