276. Paint Fence

LeetCode medium original: C# #csharp #dynamic-programming #leetcode #medium

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

LeetCode Static

Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:

Каждый столб должен быть окрашен в один цвет.

Не может быть трех или более подряд идущих столбцов одного цвета.

given два целых числа n и k, return количество способов покрасить забор.

例:

Input: n = 3, k = 2

Output: 6

Explanation: All the possibilities are shown.

Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

C# 解法

照合済み/オリジナル

public class Solution {
    public int NumWays(int n, int k) {
        if (n == 1) return k;
        
        int twoPostsBack = k;
        int onePostBack = k * k;
        
        for (int i = 3; i <= n; i++) {
            int curr = (k - 1) * (onePostBack + twoPostsBack);
            twoPostsBack = onePostBack;
            onePostBack = curr;
        }
        
        return onePostBack;
    }
}

C++ 解法

自動ドラフト、提出前に確認

#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:
    public int NumWays(int n, int k) {
        if (n == 1) return k;
        
        int twoPostsBack = k;
        int onePostBack = k * k;
        
        for (int i = 3; i <= n; i++) {
            int curr = (k - 1) * (onePostBack + twoPostsBack);
            twoPostsBack = onePostBack;
            onePostBack = curr;
        }
        
        return onePostBack;
    }
}

Java 解法

照合済み/オリジナル

class Solution {
    public int numWays(int n, int k) {
        if (n == 1) return k;
        
        int twoPostsBack = k;
        int onePostBack = k * k;
        
        for (int i = 3; i <= n; i++) {
            int curr = (k - 1) * (onePostBack + twoPostsBack);
            twoPostsBack = onePostBack;
            onePostBack = curr;
        }
        
        return onePostBack;
    }
}

JavaScript 解法

照合済み/オリジナル

var numWays = function(n, k) {
    if (n === 1) {
        return k;
    }
    
    let twoPostsBack = k;
    let onePostBack = k * k;
    
    for (let i = 3; i <= n; i++) {
        let curr = (k - 1) * (onePostBack + twoPostsBack);
        twoPostsBack = onePostBack;
        onePostBack = curr;
    }
    
    return onePostBack;
};

Python 解法

照合済み/オリジナル

class Solution:
    def numWays(self, n: int, k: int) -> int:
        if n == 1:
            return k
        
        twoPostsBack = k
        onePostBack = k * k
        
        for i in range(3, n + 1):
            curr = (k - 1) * (onePostBack + twoPostsBack)
            twoPostsBack = onePostBack
            onePostBack = curr
        
        return onePostBack

Go 解法

照合済み/オリジナル

func numWays(n int, k int) int {
    if n == 1 {
        return k
    }
    
    twoPostsBack := k
    onePostBack := k * k
    
    for i := 3; i <= n; i++ {
        curr := (k - 1) * (onePostBack + twoPostsBack)
        twoPostsBack = onePostBack
        onePostBack = curr
    }
    
    return onePostBack
}

Algorithm

1️⃣

Инициализация и 定義 вспомогательной функции:

Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.

Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2️⃣

実装 базы и проверка кэша:

В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.

Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3️⃣

Расчет с использованием рекуррентного соотношения:

В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.

Вызвать и вернуть totalWays(n).

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。