为什么我对3个序列的最长公共子序列的逻辑不健壮?

yizd12fk  于 2021-07-05  发布在  Java
关注(0)|答案(1)|浏览(345)

**结束。**此问题需要详细的调试信息。它目前不接受答案。
**想改进这个问题吗?**更新问题,使其成为堆栈溢出的主题。

4个月前关门了。
改进这个问题
我有一个关于这个问题和我的解决方案的问题。给定三个序列a,b,c-i使用逻辑求每对(a,b),(b,c)和(c,a)的最长公共子序列值。然后找出三者中的最小值。它应该给我们最长的公共子序列值。
我想知道为什么我的解决方案不可靠?下面是我使用的代码(java)。
驱动程序代码:

  1. int result1 = DynamicProgramming.longestCommonSequence(a, b);
  2. int result2 = DynamicProgramming.longestCommonSequence(b, c);
  3. int result3 = DynamicProgramming.longestCommonSequence(c, a);
  4. int temp = Math.min(result1, result2);
  5. System.out.println(Math.min(result3, temp));

程序逻辑:

  1. public static int longestCommonSequence(int[] a, int[] b) {
  2. int[][] aS = new int[a.length + 1][b.length + 1];
  3. int tempAS;
  4. for (int i = 0; i < aS.length; i++)
  5. for (int j = 0; j < aS[0].length; j++) {
  6. if (i == 0) {
  7. aS[i][j] = j;
  8. } else if (j == 0) {
  9. aS[i][j] = i;
  10. } else {
  11. int ins = aS[i][j - 1] + 1;
  12. int del = aS[i - 1][j] + 1;
  13. int mat = aS[i - 1][j - 1];
  14. tempAS = Math.min(ins, del);
  15. if (a[i - 1] == b[j - 1])
  16. aS[i][j] = Math.min(mat, tempAS);
  17. else
  18. aS[i][j] = tempAS;
  19. }
  20. }
  21. return (a.length + b.length - aS[a.length][b.length]) / 2;
  22. }

这个程序适用于我尝试过的所有测试用例。但当我把它提交给在线自动测试仪时,它在最后一个测试用例(edx课程)中失败了。我想不出解决办法会失败的情况。任何帮助都将不胜感激。
我们可以假设所有输入值都是有效整数,数组a、b、c都不是空的。
附言:我已经找到了另外一种通过所有测试的解决方案。但我很想知道我逻辑上的缺陷。谢谢。

gz5pxeao

gz5pxeao1#

如果字符串a是aaaaaaaabbbbb
b串是bbbbbbccccccc
字符串c是ccccccaaaaaaaa
则(a,b)具有长度为7的公共子序列,(b,c)具有长度为7的公共子序列,(c,a)具有长度为7的公共子序列
但是否有一个子序列是所有3个共同的呢(回答:不。。。所以只取3对比较的最小值的想法是有缺陷的)

相关问题