【問題】回搠

[davidhex 10]

這版實在有點空虛...

所以我就來問個問題吧

回碩的真諦是什麼呢.....?

有人可以說明嗎?

之前我再寫一些DP的問題的時候

因為要列出所有解

所以又用了回搠再跑一次

但後來想想這樣做還挺白痴的

所以回碩的真正用法...是什麼?

用DP的來做所有最佳解的做法是什麼....?

舉個例子...

LCS用DP算可以找出最長的字串長度

但是如果最長解有兩種以上可能的話

怎麼只用DP做

[SRX 10]

最初由 davidhex 發表

這版實在有點空虛...

所以我就來問個問題吧

回碩的真諦是什麼呢.....?

有人可以說明嗎?

之前我再寫一些DP的問題的時候

因為要列出所有解

所以又用了回搠再跑一次

但後來想想這樣做還挺白痴的

所以回碩的.............(論壇訊息:引文過長 恕刪)

沒什麼真諦

你所謂的回碩是指trackback

只是dp完之後要找出最佳解的細節

而且從結果紀錄這個點是從哪裡來的

然後利用stack的技巧 到之前那個點一直連貫找出細節

就我所知

如果你要找出所有最佳解

dp的紀錄trackback是不夠的

而且真的要找出所有解

時間複雜度也會很高

應該沒什麼題目是dp又要找出所有答案吧

如果要的話也要用recursion

[電腦狂 10]

對於LCS用DP求解還要找出最佳解的方法我寫過一次

那時是用紀錄陣列法，即在第一次跑DP時就將最佳解路徑記錄在另一張2為陣列中

等跑完後再用另外一個迴圈砲回去，這時就要依據紀錄陣列的值來走

如果可以用指標寫~應該會更好吧~因為我寫這個的時候是用VB~而他沒有指標 = =|||||

[davidhex 10]

我的回搠是用遞回寫的= =a

[SRX 10]

用lcs dp 的特性去 trackback 就不需要額外的空間了