[C言語]伯俊2579:階段を登る
構想
わかりません.dp部分なので保存しながら歩くのが当たり前ですが、入力値をあげ続けながら最大値を計算していくのは分かりますが、点火方式は分かりません.
前の質問のように明確にしたいのですが、2コマ3連続階段を踊れません...点火式のルールが見つかりませんでした.
検索することで、点火式だけがヒントを得ました.
例えば、4格子と仮定すると、
このように最後の階段を踏む条件があるので、状況の数はこうです.
しかし、最大値を求めます.したがってOXOO,XOXOでは無条件OXOOが大きい.だから2つに分けることができます.
OOXO->最後の階段を踏まなかった.そこで、最後の前段の最大値を求め、最後の段の値を加算します.->dp[i] = dp[i - 2] + input[i]
OXOO->最後の一歩を踏み出した.そこで,最後の前段階までの最大値を求め,最後の前段階,最後の段階を加える.dp[i] = input[i - 1] + input[i], dp[i - 3]
私が解読したコード
#include <stdio.h>
int max(int a, int b)
{
return a > b ? a : b;
}
int main()
{
int i, n;
int input[301];
int dp[301];
scanf("%d", &n);
i = 1;
while (i <= n)
{
scanf("%d", &input[i]);
i++;
}
dp[1] = input[1];
dp[2] = input[1] + input[2];
i = 3;
while (i <= n)
{
dp[i] = max(dp[i - 2] + input[i], dp[i - 3] + input[i - 1] + input[i]);
i++;
}
printf("%d", dp[n]);
}Reference
この問題について([C言語]伯俊2579:階段を登る), 我々は、より多くの情報をここで見つけました https://velog.io/@kimmainsain/C언어-백준-2579-계단-오르기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol