Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- long long getWaysToTile(int n, vector<long long> &memo){
- // there could be one more base case, n == 0, no way to tile it, which can be done in 1 way, don't tile it; if(n == 0) return 1;
- // base case
- if(n == 1 || n == 2){
- return n;
- }
- if(memo[n] != -1){
- return memo[n];
- }
- long long verticallyPlaced = 0, horizontallyPlaced = 0;
- // 2 * 1
- // multiplied by 1 as: number of ways to tile [2 * 1](if placed vertically) * number of ways to tile [2 * (N - 1)]
- //ways to tile 2 * 1 = 1; place one tile vertically
- verticallyPlaced = 1 * getWaysToTile(n - 1, memo);
- // 1 * 2
- // multiplied by 1 as: number of ways to tile [2 * 1](if placed horizontally) * number of ways to tile [2 * (N - 2)]
- //ways to tile 2 * 1 = 1; place 2 tiles horizontally, but there is only way to do it as the tiles are same
- horizontallyPlaced = 1* getWaysToTile(n - 2, memo);
- return memo[n] = verticallyPlaced + horizontallyPlaced;
- }
- long long getWaysToTileDP(int n){
- // 1. Storage & Meaning - dp[i] = number of ways to tile 2 * i board
- vector<long long> dp(n + 1, - 1);
- //2. Direction - smallest problem at dp[0] = 1, dp[1] = 1, dp[2] = 2;
- // - largest problem at dp[n] = ways to tile 2 * N
- // travel from smallest to largest problem
- dp[0] = dp[1] = 1;
- dp[2] = 2;
- //3. Travel & Solve
- // Check tree, what subproblems do the state(n) calls to, replicate the same in the loop
- for(int i = 3; i <= n; i++){
- dp[i] = dp[i - 1] + dp[i - 2];
- }
- return dp[n];
- }
- int main() {
- // your code goes here
- int n;
- cin >> n;
- vector<long long> memo(n + 1, -1);
- cout << getWaysToTile(n, memo) << '\n';
- cout << getWaysToTileDP(n) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
