白駿-11726

1104 ワード
白駿 アルゴリズム#アルゴリズム# DP テキストリンク

質問する


2×nサイズ1の矩形×2, 2×タイルで充填する方法の数を求めるプログラムを作成してください.
下図2×5長方形を充填する方法の一例.

入力


最初の行はnです.(1 ≤ n ≤ 1,000)

しゅつりょく


1行目2×n矩形を充填する方法数を10007で割った後、残りを出力する.

に答える


コード#コード#

#include <iostream>
using namespace std;

long long dp[1001];

int main()
{
	int n;
	scanf("%d", &n);

	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[n] << endl;
	return 0;
}
最初は、dp配列でiが奇数ならi-1配列に+1、偶数ならi/2列に*2、それから+1を加えればいいと思っていましたが、間違っていました.
だからグーグル検索の結果、dp[i-1]+dp[i-2]を作ればいいということになりました.
最初は分からなかった.
私は絵を描きました.分かりました.

[i-1]では右側の末尾が縦に、[i-2]では右側の末尾が横になります.これで自動的に終了するので[i-1]+[i-2]の点火式が建立されました.
Java同時プログラミング実践——読書ノート(一)
[アルゴリズム]K個