推 zxm20243 :推，好招 02/01 19:53
dp記結尾
令 a[n][0] 表示長度 n 結尾 0 的個數
a[n][1] 1
a[n][2] 2
a[1][0] = a[1][1] = a[1][2] = 1
可得
a[n][0] = a[n-1][0] + a[n-1][1] + a[n-1][2] // 0 隨便接
a[n][1] = a[n-1][0] + a[n-1][2] // 不可接 1
a[n][2] = a[n-1][0] + a[n-1][1] // 不可接 2
變數變換一下
令 c[n] := a[n][0] + a[n][1] + a[n][2], 所以
c[n] = a[n][0] + a[n][1] + a[n][2]
= 3a[n-1][0] + 2a[n-1][1] + 2a[n-1][2]
= 2c[n-1] + a[n-1][0]
= 2c[n-1] + c[n-2]
※ 引述《wsx02 ()》之銘言：
: 請問一題今天台大的考題
: 三元n序列 有0,1,2三種字元
: 不包含連續1和連續2的遞迴式
: 為什麼是a(n) = 2a(n-1) + a(n-2)
: //還是 a(n) = a(n-1) + 2a(n-2) ... 我忘記這兩個是哪一個了@@
: 請問應該要怎麼導出來呢?
: 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.47.38