發表新討論
#25216: 分享一下解法


daniel0803 (yoru)

學校 : 新北市私立時雨高級中學
編號 : 140416
來源 : [140.112.24.96]
最後登入時間 ：
2022-09-28 19:45:48
d389. 11069 - A Graph Problem -- UVa11069 | From: [1.200.106.212] | 發表日期 : 2021-04-30 16:28

dp為方法數，dp[節點數][最後一個節點取或不取(0和1表示)]

dp[n][0]=dp[n-1][1](第n個不取則第n-1個必須取）

dp[n][1]=dp[n-2][0]+dp[n-2][0]+dp[n-2][1](第n個取則第n-2個可取可不取）

dp[n][0]+dp[n][1]即是n個節點時的總方法數

 
#25217: Re:分享一下解法


daniel0803 (yoru)

學校 : 新北市私立時雨高級中學
編號 : 140416
來源 : [140.112.24.96]
最後登入時間 ：
2022-09-28 19:45:48
d389. 11069 - A Graph Problem -- UVa11069 | From: [1.200.106.212] | 發表日期 : 2021-04-30 18:33

dp為方法數，dp[節點數][最後一個節點取或不取(0和1表示)]

dp[n][0]=dp[n-1][1](第n個不取則第n-1個必須取）

dp[n][1]=dp[n-2][0]+dp[n-2][1](第n個取則第n-2個可取可不取）

dp[n][0]+dp[n][1]即是n個節點時的總方法數

 
ZeroJudge Forum