dp_1. ネットワーク線のクリップ

2044 ワード
テキストリンク

感じた21年10月4日


  • 根本的に問題を見て、どのように解答するか分かりません.
    これを一人ずつやってみませんか.感じさせる

  • 入力は7、出力は21、7を1、2に変換
    いちいち確認するのは難しい.21回確認する必要があります.
    ->このような場合、本当に直感的にフラッシュしなければなりません!
    =>プログラミングでは考えられません.
    まず考えなければならない.
    例の5つの例に惑わされてはいけない...
    小さな職場でやりましょうか.明らかに思い出せないけど...
    ネットワーク線が1の場合、1に切り分けることができます.->1つ
    ネットワーク線が2の場合、1+1/2にカットできます.->2つ
    ネットワーク線が3の場合、1+1+1+2+1->が3本あります
    ネットワーク線が4の場合、1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
    //2/2+2->計5個
    やってみるとルールが見つかりました...

    • 再帰使用時


  • まず絵を描くとこうなります.典型的な回帰計算のdfs問題.
  • 注意すべき点は、どこでカウントするかです.
    画像を見れば、どこで時間を計るのが正しいかがわかります.
  • の再回帰を続行する場合は、例外の処理に注意してください.ネットワーク線は負数にならないことに注意してください.

    • ポリシー


  • 再帰の使用

    ->消せば耳が使えるらしい.

  • dpの使用
    :作成方法が分からない場合は、偶数を作成します.

    • ->点火式を作ることができます.
    d[3] = d[1] + d[2];
    d[4] = d[3] + d[2];

    ソースコード

  • 在貴
    • void recur(int n, int&cnt)
{
	if (n == 0)
	{
		cnt++;
		return;
	}

	if(n - 1 >= 0)
		recur(n - 1, cnt);
	if (n - 2 >= 0)
		recur(n - 2, cnt);


}


int main(void)
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);	
	
	int n;
	cin >> n;
	int cnt = 0;
	recur(n, cnt);
	cout << cnt;
	return 0;
}
  • dp; 
    • int main(void)
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);	
	
	int n;
	cin >> n;
	int cnt = 0;

	vector<int>dp(n);

	dp[0] = 1;
	dp[1] = 2;
	for (int i = 2; i < n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cout << dp[n -1];
	return 0;
}
    [白準/11000]教室の手配(Java)
    Spring Web開発基盤