[LeetCode] 276。フェンスをペイントするフェンスをペイントする

276 Paint Fence Painting Fence

n本の支柱がある柵があり、各支柱はk色のいずれかで塗装できます。

隣接する2つ以下の柵の支柱が同じ色になるように、すべての支柱をペイントする必要があります。

柵をペイントできる方法の総数を返します。

注意：
nとkは非負の整数です。

問題解決のアイデア：

動的計画法（DP）を使用すると、2つ以上の連続する列を色にすることはできません。つまり、3番目の柱、ルートの最初の柱は色ではなく、2番目の柱は色ではありません。前の色が同じでない場合、色を計算する可能性、つまりk-1の可能性を取り除くために必要な時間。 dp [1]が最初の列であり、塗装されるまでの可能性の数dp [2]であり、2番目の列が塗装されるまでの可能性の数であると仮定します。dp[3] =（k-1）* dp [1 ] +（k-1）* dp [2]。

基本ケースの下でさらに説明する再帰を使用すると、すべてのルートの最初の列はkペイントされます。2番目の実施形態は、最初と2番目の列が同じルートを作成できるため、ルートの色がk * kです。

状態：dp [i] //ブラシメソッドの総数を杭打ちするi番目のペイントを表します

関数：dp [i] = dp [i-1] *（k-1）+ dp [i-2] *（k-1）

初期化：dp [0] = k、dp [1] = k + dp [0] *（k-1）= k * k

戻り値：dp [n]

Java：時間：O（n）、スペース：O（n）

public class Solution { public int numWays(int n, int k) { int dp[] = new int[n + 1] dp[0] = 0 dp[1] = k dp[2] = k * k if(n <= 2){ return dp[n] } for(int i = 2 i < n i++){ dp[i] = (k - 1) * (dp[i - 1] + dp[i - 2]) } return dp[n] } }

Java：時間：O（n）、スペース：O（1）

public class Solution { public int numWays(int n, int k) { int dp[] = {0, k , k*k, 0} if(n <= 2){ return dp[n] } for(int i = 2 i < n i++){ dp[3] = (k - 1) * (dp[1] + dp[2]) dp[1] = dp[2] dp[2] = dp[3] } return dp[3] } }