プログラマーはいくつかの練習問題を作ってみた.

[問題]2 x nタイル

説明:

長方形のタイルがあり、横方向の長さは2、縦方向の長さは1です.この矩形タイルを用いて床を充填し,床の長手方向長さは2,横方向長さはnである.タイルを充填するには2つの方法があります.
タイルを水平に置くとき
タイルを垂直に置く場合
例えば、nが7の矩形を以下のように充填することができる.

矩形の横方向の長さnをパラメータとして指定した場合、解関数を完了し、矩形を埋め込む方法の数を返します.
せいげんじょうけん
横長nは60000以下の自然数である.
状況の数が多くなる可能性があるので、状況の数を1000000 7で割って残りを返してください.

解法

鐘万北252 pも同様の問題があるので、簡単に解けます.
完全探索を用いてすべての答えを作成し,個数の関数を計算し,注釈を用いて動的計画法に変換する.この場合の数を計算する場合は、常に2つのプロパティをチェックします.
2つの分類には、平らな方法が含まれています.
2つの分類に含まれるタイリング方法はありません.
一部の問題分割が最初の条件に違反すると,アルゴリズムは実際の数より少ない答えを与える.
前後が同じだと思うので、数えたいです.
逆に、2つ目の条件に違反すると、実際よりも多くの答えが得られます.すべての数字を数えたいのに、繰り返しが許されるからです.幸いにもこの問題には二つの性質がある.そのため、2枚のタイルで覆うかどうかを決めるだけです.
Tiling(n)=2*nはタイルで長方形を覆う方法を返します.
tiling(n) = tiling(n-1) + tiling(n-2)
これはこれによって書かれたコードです.

#include <string>
#include <vector>

using namespace std;

const int mod = 1000000007;
int cache[60000];

int tiling(int width){
  if(width <= 1) return 1;
  
  int& ret = cache[width];
  if(ret != 0) return ret;
  return ret = (tiling(width-2) + tiling(width-1)) % mod;
}

int solution(int n) {
  int answer = 0;
  answer = tiling(n);
  return answer;
}