✅ 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(再帰)で展開するか