为什么需要动态编程呢？

Question

问题陈述可以在这里找到.它说DP解决方案需要O(m*n)时间.但为什么我们需要DP呢？我写了以下解决方案,但不确定是否需要DP.

    String str1,str2;
    str1 = "OldSite:GeeksforGeeks.org";
    str2 = "NewSite:GeeksQuiz.com";

    int i,j,k;
    int count,currentMax =0;
    for(i = 0; i < str1.length();i++){
        count = 0;
        k = i;
        for(j = 0; j < str2.length() && k < str1.length();j++){
            if(str1.charAt(k) == str2.charAt(j)){
                count++;
                k++;
            }
            else if(count > currentMax)
                    currentMax = count;
            continue;
        }
        if(count > currentMax)
            currentMax = count;
    }

    System.out.println(currentMax);

即使我的解决方案需要O(m*n),但我似乎没有采用DP方式.

我所做的是检查string1中的每个字符,字符串2中可用的最大长度是多少.

基本上我认为这是蛮力方法.

我的解决方案有什么问题吗？

编辑在评论部分提到.

进行更改以产生正确的结果,将内部for循环更改为

for(j = 0; j < str2.length() && k < str1.length();j++){
            if(str1.charAt(k) == str2.charAt(j)){
                count++;
                k++;
            }
            else if(count > currentMax){
                    currentMax = count;
                    count = 0;
                                            k=i;
            }
            else{
                count = 0;
                                    k=i;
                            }
            continue;
}

编辑2评论.

for(j = 0; j < str2.length() && k < str1.length();j++){
            if(str1.charAt(k) == str2.charAt(j)){
                count++;
                k++;
            }
            else if(count > currentMax){
                    currentMax = count;
                    count = 0;
                    k=i;
                    if(str1.charAt(k) == str2.charAt(j)){
                        count++;
                        k++;
                    }
            }
            else{
                count = 0;
                k=i;
                if(str1.charAt(k) == str2.charAt(j)){
                    count++;
                    k++;
                }
            }
            continue;
        }

Answer 1

我认为你的代码最长的常见子串是不工作尝试输入: -

str1 = "swring";
str2 = "skwkring";

这里最长的公共子串是"ring",它是4个字符,但是你的代码给出了"6"的答案.在这里,我认为你的代码只是计算字符串中的常见字符"swring",因此结果为6.

你不能用O(n*m)中的强力来解决这个问题,尽管看起来很明显,所以使用了DP.

编辑: -

您编辑的解决方案涵盖了更多问题,但仍然不适合集中定位的字符串,原因与DP不同,它是贪婪的

检查: -

str1 = "sbsringada";
str2 = "cdssringasd";

正确的答案是6,"sringa"但代码输出5.原因是它在str2 之前在"s" 变得贪婪"sringa".

编辑:-

除非你没有找到实际的暴力算法或证明你的代码在数学上是正确的,否则这将永远继续你将给出一个代码我会给你的代码.

由于你还没有证明,我会给你一个我曾经为同样的问题写过的实际蛮力代码.理解起来非常简单直观,但效率非常低.

伪代码: -

int max = 0;

for(int i=0;i<str1.length,i++) {

 for(int j=0;j<str2.length;j++) {
    int k = 0;  
    for(;j+k<str2.length && i+k < str1.length ;k++) {
        if(str1[i+k]!=str[j+k]) 
           break;
    }

    if(k>max)
        max = k;
 }


}

print(max);

这段代码的时间复杂度 O(m*n*min(m,n))

为了取得进一步的进展,您需要证明您的代码与此类似,就像DP的情况一样,通过归纳证明了这一点.