algorithm - 無の数の数え方は 1 つですか?

Question

これは、問題を解決しているときに私が日常的に間違えるものです。引数が最下位にある場合、再帰関数の値をどのように決定するのでしょうか。例が役立ちます：

n を指定して、2x1 ブロックのみを使用して 3xN グリッドをタイル化する方法の数を見つけます。ブロックの回転が許可されます。

DP ソリューションは、次のように簡単に見つけることができます。

f(n): 3xN グリッドをタイル化する方法の数

g(n): 3xN グリッドを、1x1 ブロックを右端の列で切り取って並べる方法の数

f(n) = f(n-2) + 2*g(n-1)

g(n) = f(n-1) + g(n-2)

私は当初、基本ケースは f(0)=0、g(0)=0、f(1)=0、g(1)=1 になると考えていました。しかし、これは間違った答えをもたらします。次に、どこかで f(0)=1 を読み、次のように推論しました。

タイル (2x1 ブロック) を使用できない方法は 1 つしかないため、3x0 グリッドをタイル化する方法は 1 つです。

私の質問は、その論理により、g(0) も 1 であってはならないということです。しかし、正しい解では g(0)=0 です。一般に、何も使わない方法が 1 つあると言えるのはいつですか。

Answer 1

タイリングに関する具体的な質問については、次のように考えてください。

• 「3*0 グリッドを並べる」方法はいくつありますか?
  私はこう言います：ただ一方的に、何もしないでください！他の方法では「何もしない」ことはできません。(f(0) = 1)

• 「特定のブロックを切り離して 3*0 グリッドを並べる」方法はいくつありますか?
  私はこう言います：ねえ！それ無理！何もないので、特定のブロックを切り離すことはできません。ですから、とにかくそのタスクを解決できる方法はありません。(g(0) = 0)

それでは、一般的なケースに移りましょう。

• ゼロケースについての「一般的な」ルールはありません。
• 問題によっては、何らかの方法で状況を「解釈」し、妥当な値を見つけることができる場合があります。ほとんどの場合(「方法」の定義によって異なります)、「何もしない」方法の数は 1 であり、不可能なことを行う方法の数は 0 です。
• 警告！どういうわけかゼロケースを「解釈」できるだけでは、関係を正しくするには十分ではありません! ほとんどの場合、これは「トリッキーな」ケースになるため、再帰関係 (つまり、前の値から n 番目の値を取得する方法) が 0 対 1 の場合にも適用できるかどうかを再確認する必要があります。
• ゼロケースが扱いにくい、または混乱している場合は、ゼロ以外のケースに基づいて再帰関係を作成する方が簡単な場合があります。

Answer 2