Prerequisite : - Basic Dynamic programming
Problem : - Given an integer N, representing the number of tiles. There are basically two types of tiles: 1 and 0. All the 0 types of tiles exist in pairs. Print how many possible arrangements you can form using these tiles.
Explanation :-
Finding the dependency of the previous state on the current state will help us solve this problem, which falls under dynamic programming.
Intuition: The total number of combinations to form n tiles is equal to the sum of the total number of combinations to form (n-1) tiles and the total number of combinations to form (n-2) tiles. We can achieve this by adding tile 1 to all combinations of (n-1) tiles and tile 00 to all combinations of (n-2) tiles.
Algorithm :-
Initialize the value of base state dp[1] = 1(only one combination is possible from 1 tile which is 1) and dp[2] = 2(two combinations are possible from two tiles 11 and 00) .
Use the previous dp states to find the further states and keep on finding the next states until you reach n, dp[n] = dp[n-1]+dp[n-2].
Continuously apply the modulus operation with 15746 to your resulting dynamic programming state.
C++ Solution : -
#include <iostream>
using namespace std;
int main() {
// your code goes here
int n;
cin>>n;
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=n;i++)
{
dp[i] = (dp[i-1] + dp[i-2]) % 15746;
}
cout<<dp[n]%15746<<endl;
return 0;
}