BOJ-9095 1,2,3プラス

1138 ワード
algorithm boj テキストリンク

必要な知識

  • 動的計画法

    • に近づく

  • 点火式
    • dp[i] = dp[i-1]+dp[i-2]+dp[i-3]
    dp[i]:i怠惰を1,2,3の和にする方法数
  • iが1,2,3の場合、それぞれ1,2,4に初期化される.

    • コード(C+)

    #include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int dp[15];
int go(int i) {
	if (i == 1) return 1;
	if (i == 2) return 2;
	if (i == 3) return 4;
	int& ret = dp[i];
	if (ret != -1) return ret;
	ret = 0;
	return ret = go(i - 1) + go(i - 2) + go(i - 3);
}
int main() {
	int n, x;
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		printf("%d\n", go(x));
	}
	return 0;
}
    簡単なjs
    JavaScript 2. 関数宣言と関数出力