從表中尋找最長公共子序列

Question

我對LCS問題兩個輸入字符串： 1：ABCDGH 2：AEDFHR

下表表示動態規劃解自下而上表的長度瀕海戰鬥艦的：

基於試圖找到在LCS實際字母時this video提供的方法，您從表的末尾開始，往後走。如果左側和右側的單元格與當前單元格不同，並且單元格對角線的單元格更少，則您知道當前列中的字符已包含在內，並且您沿對角線向後移動。否則，你要麼移動到左邊，要麼移動到右邊。 （H，R），（H，H），然後到（F，G）。但是一旦你到達那裏，算法會如何決定下一步去哪裏？看起來它應該向左走，因爲這會導致從下一列到左側的LCS中包含「D」，但是（F，G）的左側，右側和對角線上的單元都具有值2而對角線的細胞並不少。 那麼算法中的邏輯應該是什麼情況下，如果你有一個單元格由相同的值包圍？

Answer 1

動態規劃問題通常有多種最優解決方案。當兩個或三個相鄰小區具有相同的值時，它們同樣好，如果該值也是相鄰小區中最好的一個，則跳轉到其中任何一個將導致最佳解決方案之一。 （請注意，您的問題陳述可能會施加其他約束，例如「如果有多個最佳解決方案，請選擇最後一個替代方案儘可能早的方案」。）