推 sixB: 算數學移項 哇啊啊啊>< 05/06 00:49
→ sixB: 你根本就是天才 05/06 00:49
然後我看不懂為什麼可以 dp[n-1]*2 + dp[n-3]
https://i.imgur.com/ryRR56z.png
你從這張圖可以推導出來
dp[i][0] = dp[i-1][0] + dp[i-2][0] + 2*dp[i-1][1] ---(1)
dp[i][1] = dp[i-2][0] + dp[i-1][1] ---(2)
目標是推導出
dp[i][0] = 2*dp[i-1][0] + dp[i-3][0]
你把(2)帶到(1)可得
dp[i][0] = dp[i-1][0] + dp[i-2][0] + 2*dp[i-3][0] + 2*dp[i-2][1]
稍微移動一下
dp[i][0] = dp[i-1][0] + dp[i-3][0] + (dp[i-2][0] + dp[i-3][0] + 2*dp[i-2][1])
括號裡面等於dp[i-1][0]
所以 dp[i][0] = 2*dp[i-1][0] + dp[i-3][0]
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1746462095.A.0D2.html