Count ways to tile an N | C ++ Program to implement the above approach ; Function to count the ways to tile N * 1 board using 1 * 1 and 2 * 1 tiles ; dp [ i ] : Stores count of ways to tile i * 1 board using given tiles ; Base Case ; Iterate over the range [ 2 , N ] ; Fill dp [ i ] using the recurrence relation ; Driver Code ; Given N ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; long countWaysToTileBoard ( long N ) { long dp [ N + 1 ] ; dp [ 0 ] = 1 ; dp [ 1 ] = 2 ; for ( int i = 2 ; i <= N ; i ++ ) { dp [ i ] = ( 2 * dp [ i - 1 ] + dp [ i - 2 ] ) ; } cout << dp [ N ] ; } int main ( ) { long N = 2 ; countWaysToTileBoard ( N ) ; return 0 ; }