→ suhang: okok tks, 我讀讀，感謝 04/26 04:02
推 eight0: aababb 只要交換一次，但你的方法給 2 04/26 17:42
推 eight0: 可能要排列組合出所有目標，再找和初始狀態距離最短的 04/26 17:45
問最小交換次數，使字元兩兩一致
例如 abcabc -> aabbcc or bbaacc or ccaabb 皆可
https://paste.ubuntu.com/p/4g2wbn5S2P/
這題感覺好像DP, 但不知道怎麼DP
我寫了一個recursie, 可以找到aabbcc但是又無法證明這是"最小"次數
從 i = 0開始，
如果 s[i] != s[i+1] 那就開始線性搜尋可以交換的字元，交換之後遞歸往下
我這個做法是greedy嗎？
遇到不相同字元，去找最近可以交換過來的字元，(感覺很貪婪)
(我一直很不了解greedy的精神)
請問這題該怎麼解呢? tks
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.189.14.17
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1556080532.A.3B1.html