[boj](s 3)90951,2,3プラス

1449 ワード
boj テキストリンク
✅ DP

質問する


リンク


1.問題のアクセスと解決ロジック


構成数字が同じであっても,順序が異なるものは異なる組合せである.
したがって、f(n)f(n)f(n)f(n)nは、整数nnnが1、2、3の和である方法数を表す.
何か手に入れられるなら
f(1)=1f(1)=1f(1)=1
{1}
f(2)=2f(2)=2f(2)=2
{1,1}
{2}
f(3)=4f(3)=4f(3)=4
{1,1,1}
{1,2}
{2,1}
{3}
f(4)=7f(4)=7f(4)=7
{1,1,1,1}
{1,2,1}
{2,1,1}
{1,1,2}
{3,1}
{1,3}
{2,2}
ここでは、次のルールが見つかります.
f(4)=f(3)+f(2)+f(1)=4+2+1=7f(4)=f(3)+f(2)+f(1)=4+2+1=7f(4)=f(3)+f(2)+f(1)=4+2+1=7
だから点火式.
f(n)=f(nέ1)+f(nή2)+f(n)=f(n-1)+f(n-2)+f(n-3)=f(nέ1)+f(nή2)+f(nί3).

ぎじふごう


定義

  • f(n)f(n)f(n)f(n)f(n):整数nnnが1、2、3の和であることを示す方法数
  • の答え
    f(n)f(n)f(n)
  • 初期値
    f(1)=1f(1)=1f(1)=1
    f(2)=2f(2)=2f(2)=2
    f(3)=4f(3)=4f(3)=4
  • 点火式
    f(n)=f(n−1)+f(n−2)+f(n−3),(n>3)f(n)=f(n-1)+f(n-2)+f(n-3),(n>3)f(n)=f(n−1)+f(n−2)+f(n−3),(n>3)

    • 2.コード


    3.時間複雑度分析


    私たちはすべての状況を見つけます.
    O(N)O(N)O(N)

    4.問題の重要な部分


    DP問題で重要なのは,点火式の導出である.
    オプションはBootm Up(繰り返し文)で展開するか、Top Down(再帰)で展開するか
    優先順位キューPriorityQueueテストは、自動的にソートされます.
    testNGテストで簡単な同時テストができます