作者suhang (suhang)
看板Python
标题[问题] 最小交换次数使字元两两一致
时间Wed Apr 24 12:35:29 2019
问最小交换次数，使字元两两一致
例如 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://webptt.com/cn.aspx?n=bbs/Python/M.1556080532.A.3B1.html
2F：→ suhang: okok tks, 我读读，感谢 04/26 04:02
3F：推 eight0: aababb 只要交换一次，但你的方法给 2 04/26 17:42
4F：推 eight0: 可能要排列组合出所有目标，再找和初始状态距离最短的 04/26 17:45