～技术宅真可怕～#1 - 2019-4-3 23:02
かがや (障子を開けよ、外の世界は広いぞ~)
有一串正整数数组，每次可以去掉一个数，或一个回文数子串，剩下的数顺序不变组成一个新数组，然后重复上面步骤，最少需要几次可以让数组为空？
目前考虑是分两种情况取最小值的推导式，来万能的bangumi问一下各位有没有更好的思路，欢迎大家讨论
/* 2019年4月4日补充 */
不好意思问题有一点没有描述清楚，稍微补充一下
这里的正整数应该小于10的
举个例子，比如初始数组为{1, 2, 3, 1, 2, 1}
第一次去掉第四个数1，得到{1, 2, 3, 2, 1}
第二次可以一次性去掉这个回文数组，所以最少为两次
目前考虑的转移式 f[i, j]=min(f[t-1] + f[t+1][j], f[i + k, j - k])
其中t是i到j之间，k是从i往后和从j往前最长能够构成回文的长度
一晚上能收到这么多回复有点吃惊，我会好好思考一下大家的想法，再次十分感谢大家
目前考虑是分两种情况取最小值的推导式，来万能的bangumi问一下各位有没有更好的思路，欢迎大家讨论
/* 2019年4月4日补充 */
不好意思问题有一点没有描述清楚，稍微补充一下
这里的正整数应该小于10的
举个例子，比如初始数组为{1, 2, 3, 1, 2, 1}
第一次去掉第四个数1，得到{1, 2, 3, 2, 1}
第二次可以一次性去掉这个回文数组，所以最少为两次
目前考虑的转移式 f[i, j]=min(f[t-1] + f[t+1][j], f[i + k, j - k])
其中t是i到j之间，k是从i往后和从j往前最长能够构成回文的长度
一晚上能收到这么多回复有点吃惊，我会好好思考一下大家的想法，再次十分感谢大家
aaabaaaaaaaaaaaaaaaaaaaaaaaaaa，
直接把后面所有a全删了的话要三次，把aaabaaa删了的话只要两次。
删除aaabaaa之后递归调用下这个函数
以及删除后面a之后递归调用下这个函数
分别比较这两种情况的返回值，然后选择最小的那个值+1作为返回值。
abacadaeafag，用最长子序列要7次，但顺着删只要6次
2、a b a a d a a a
3、a b a c a d a a a
4、a b a c a d a e a a
5、a b a c a d a e a f a
6、a b a c a d a e a f a g
但个人觉得还是很奇怪，比如
abacadaeafagafd
它有多种拆法，
按照daafaad, aaa, bcegf 一共7次(这回貌似没算错吧？)
但另一边aaaaaaa, dfgfd, bce一共5次，起手长度一样，而且应该不会比7更长的子序列了？
所以说贪心往往是有问题的
我觉得如果遇到当前状态有多个长度一样的最长子序列的话，可以来个dfs搜索一下，虽然很暴力，不过我觉得平均情况下应该不会太差
不过这也只是猜想，很可能又会冒出别的问题
其实只需要额外加入5 4 5 也是两次
45541234554的最长回文子串是455414554或者455424554或者455434554。
删掉455414554，剩下23。继续找最长回文子串。
有什么问题？
所以需要寻找多重存在，那样就是 O(n^3 * 2^n)
因为保证内部一定有刚被删除的回文串，那么只需要最后删除的那个再多删前后两个就行。
而拆三段一定被拆两段覆盖到，参考 dijkstra 算法。
——
该想法已经从 #12 跑偏，转 #14。
采用 C 那样的非对称子界而非 Pascal 的对称子界（为了实现 0 长度边界）
(define f (memproc (lambda (i j)
(cond
[(= i j) 0]
[(= (1+ i) j) 1]
[(= (ref s i) (ref s j)) (f (1+ i) (- j 1))]
[else (min (map (lambda (k) (+ (f i k) (f k j))) (range (1+ i) j)))]))))
楼主发帖的当晚就有人说过这个方法了，不过貌似很快就意识到有问题然后删了
首先发现消除 b 需要 1 次（length == 1）
然后发现消除 e 需要 1 次（length == 1）
然后发现消除 be 需要 2 次（=f("b")+f("e")）
然后发现消除 c 需要 1 次（length == 1）
然后发现消除 bec 需要 3 次（=f("be")+f("c")）
然后发现消除 abeca 需要 3 次（=f("bec")）
或者说，按照 breakdown 做法
f("abeca")=f("bec") （因为 'a'=='a'）
然后就很容易地一个个去掉就行。
根本没有多段问题。
楼上的样例都加进去了。
我的想法已经从 #12 跑偏，请看 #14
解释如下：
if 长度 = 0，then 需要删除次数 = 0；
elseif 长度 = 1，then 需要删除次数 = 1 次；
elseif 长度 = 2，且两个字符相同，then 需要删除次数 = 1；
elseif 首尾两个字符相同，then 需要删除次数 = 去掉这首尾两个字符后的需要删除次数。
else 需要删除次数 = 分成两段分别求需要删除次数并相加，求其中的最小值。
改写成正常的 DP 不会花太多功夫的，记得优先求 j-i 比较小的。