790. Domino and Tromino Tiling

leetcode

#csharp#hash-table#leetcode#recursion

Task

: medium

У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.

Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.

Пример:

Input: n = 3

Output: 5

Explanation: The five different ways are show above.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    private const int MOD = 1_000_000_007;
    private Dictionary<int, int> fCache = new Dictionary<int, int>();
    private Dictionary<int, int> pCache = new Dictionary<int, int>();
    private int p(int n) {
        if (pCache.ContainsKey(n)) {
            return pCache[n];
        }
        if (n == 2) {
            return 1;
        }
        int result = (p(n - 1) + f(n - 2)) % MOD;
        pCache[n] = result;
        return result;
    }
    private int f(int n) {
        if (fCache.ContainsKey(n)) {
            return fCache[n];
        }
        if (n <= 2) {
            return n;
        }
        int result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
        fCache[n] = result;
        return result;
    }
    public int NumTilings(int n) {
        return f(n);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private const int MOD = 1_000_000_007;
    private unordered_map<int, int> fCache = new unordered_map<int, int>();
    private unordered_map<int, int> pCache = new unordered_map<int, int>();
    private int p(int n) {
        if (pCache.count(n)) {
            return pCache[n];
        }
        if (n == 2) {
            return 1;
        }
        int result = (p(n - 1) + f(n - 2)) % MOD;
        pCache[n] = result;
        return result;
    }
    private int f(int n) {
        if (fCache.count(n)) {
            return fCache[n];
        }
        if (n <= 2) {
            return n;
        }
        int result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
        fCache[n] = result;
        return result;
    }
    public int NumTilings(int n) {
        return f(n);
    }
}

Java solution

matched/original

import java.util.HashMap;
import java.util.Map;

class Solution {
    private static final int MOD = 1_000_000_007;
    private Map<Integer, Integer> fCache = new HashMap<>();
    private Map<Integer, Integer> pCache = new HashMap<>();

    private int p(int n) {
        if (pCache.containsKey(n)) {
            return pCache.get(n);
        }
        if (n == 2) {
            return 1;
        }
        int result = (p(n - 1) + f(n - 2)) % MOD;
        pCache.put(n, result);
        return result;
    }

    private int f(int n) {
        if (fCache.containsKey(n)) {
            return fCache.get(n);
        }
        if (n <= 2) {
            return n;
        }
        int result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
        fCache.put(n, result);
        return result;
    }

    public int numTilings(int n) {
        return f(n);
    }
}

JavaScript solution

matched/original

const MOD = 1_000_000_007;
const fCache = new Map();
const pCache = new Map();

function p(n) {
    if (pCache.has(n)) {
        return pCache.get(n);
    }
    if (n === 2) {
        return 1;
    }
    const result = (p(n - 1) + f(n - 2)) % MOD;
    pCache.set(n, result);
    return result;
}

function f(n) {
    if (fCache.has(n)) {
        return fCache.get(n);
    }
    if (n <= 2) {
        return n;
    }
    const result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD;
    fCache.set(n, result);
    return result;
}

function numTilings(n) {
    return f(n);
}

Python solution

matched/original

from functools import cache

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 1_000_000_007

        @cache  
        def p(n):  
            if n == 2:
                return 1
            return (p(n - 1) + f(n - 2)) % MOD

        @cache  
        def f(n):  
            if n <= 2:
                return n
            return (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD

        return f(n)

Go solution

matched/original

package main

var MOD = 1_000_000_007
var fCache = make(map[int]int)
var pCache = make(map[int]int)

func p(n int) int {
    if val, found := pCache[n]; found {
        return val
    }
    if n == 2 {
        return 1
    }
    result := (p(n-1) + f(n-2)) % MOD
    pCache[n] = result
    return result
}

func f(n int) int {
    if val, found := fCache[n]; found {
        return val
    }
    if n <= 2 {
        return n
    }
    result := (f(n-1) + f(n-2) + 2*p(n-1)) % MOD
    fCache[n] = result
    return result
}

func numTilings(n int) int {
    return f(n)
}

Explanation

Algorithm

Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).

Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор

@cache

автоматически поддерживает эти хэшмапы для нас.

Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.

😎