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

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

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

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

int result1 = DynamicProgramming.longestCommonSequence(a, b);
        int result2 = DynamicProgramming.longestCommonSequence(b, c);
        int result3 = DynamicProgramming.longestCommonSequence(c, a);

        int temp = Math.min(result1, result2);

        System.out.println(Math.min(result3, temp));

程序逻辑:

public static int longestCommonSequence(int[] a, int[] b) {

        int[][] aS = new int[a.length + 1][b.length + 1];
        int tempAS;

        for (int i = 0; i < aS.length; i++)
            for (int j = 0; j < aS[0].length; j++) {

                if (i == 0) {
                    aS[i][j] = j;
                } else if (j == 0) {
                    aS[i][j] = i;
                } else {

                    int ins = aS[i][j - 1] + 1;
                    int del = aS[i - 1][j] + 1;
                    int mat = aS[i - 1][j - 1];

                    tempAS = Math.min(ins, del);

                    if (a[i - 1] == b[j - 1])
                        aS[i][j] = Math.min(mat, tempAS);
                    else
                        aS[i][j] = tempAS;
                }
            }
        return (a.length + b.length - aS[a.length][b.length]) / 2;
    }

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

gz5pxeao

gz5pxeao1#

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

相关问题