Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- /*
- QUESTION - https://www.youtube.com/watch?v=_c_R-uIi-zU&list=PL-Jc9J83PIiG8fE6rj9F5a6uyQ5WPdqKy&index=27
- Tiling m * N board with m * 1 tiles
- */
- long long getWaysToTilemXN(int N, int &m, vector<long long> &memo){
- //base case
- if(N < m){
- // 1 way to tile, place vertically only, as you can't place horizontally, tile length(m) > board length(N)
- return 1;
- }
- if(N == m){
- // 2 ways to tile (place all horizontally or all vertically)
- return 2;
- }
- if(memo[N] != -1){
- return memo[N];
- }
- long long placedVertically = 0, placedHorizontally = 0;
- //place tile as m * 1 (vertically)
- placedVertically = 1 * getWaysToTilemXN(N - 1, m, memo);
- //place tile as 1 * m (horizontally)
- if(N >= m){
- placedHorizontally = 1 * getWaysToTilemXN(N - m, m, memo);
- }
- return memo[N] = placedVertically + placedHorizontally;
- }
- long long getWaysToTilemXNDP(int N, int m){
- if(N < m){
- //can only place vertically
- return 1;
- }
- // Storage & Meaning - dp[i] = ways to tile m * i board
- vector<long long> dp(N + 1, -1);
- /*Direction -
- Smallest Problem:
- dp[0] = dp[1] = dp[2] = dp[3] = dp[4] = ..... dp[i] = 1; i < M
- dp[i] = 2; i == M
- Largest Problem = dp[N]
- */
- for(int i = 0; i < m; i++){
- dp[i] = 1;
- }
- dp[m] = 2;
- // Travel & Solve - Travel from Smallest to Largest Problem.
- for(int i = m + 1; i <= N; i++){
- dp[i] = dp[i - 1] + dp[i - m];
- }
- return dp[N];
- }
- int main() {
- // your code goes here
- int N, m;
- cin >> N >> m;
- vector<long long> memo(N + 1, - 1);
- cout << getWaysToTilemXN(N, m, memo) << '\n';
- cout << getWaysToTilemXNDP(N, m) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
