[21416][伯俊/BOJ]9095号1.2.3プラス

1524 ワード
アルゴリズム#アルゴリズム# テキストリンク

質問する



にゅうしゅつりょく



に答える


4を1、2、3の和として表す方法は、次のとおりです.
1+1+1+1
1+2+1
2+1+1
3+1
1+1+2
2+2
1+3
全部で7種類あります.
各方法の後ろから+1,+2,+3が見える.それ以外は
3を1,2,3の和の1+1+1+2,2+13と表す
2の1、2、3の和を表す1+1、2
1を1の和として表すことができます.
すなわちd(1)+1,d(2)+2,d(3)+3である.
したがって、これを点火式、すなわちd(n)=d(n−1)+d(n−2)+d(n−3)、初期値d(1)=1、d(2)=2、d(3)=4と表す.

コード#コード#


上から下へ
#include <bits/stdc++.h>
using namespace std;

int d[102];

int dp(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	if (d[n] != 0) return d[n];

	d[n] = dp(n - 1) + dp(n - 2) + dp(n - 3);
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int n;
		cin >> n;
		cout << dp(n) << '\n';
	}
}
bottom-up方式
#include <bits/stdc++.h>
using namespace std;

int d[102];

int dp(int n)
{
	d[1] = 1; // 1+3
	d[2] = 2; // 1+1+2, 2+2
	d[3] = 4; // 1+1+1+1, 1+2+1. 2+1+1, 3+1 

	for (int i = 4; i <= n; ++i)
		d[i] = d[i - 1] + d[i - 2] + d[i - 3];
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int n;
		cin >> n;
		cout << dp(n) << '\n';
	}
}
HDu-5443-The Water Problem-裸のRMQ線分ツリー
POJ 2784 Buy or Build最小生成ツリー