首页 > 代码库 > 编程之美--3.3

编程之美--3.3

2024-07-09 07:13:02   229人阅读

题目描述：计算相似度，其实本质就是计算编辑距离

思路：一开始先递归，然后加备忘改DP，发现有很多重复子问题，再重新设计dp算法

  1 #include <iostream>  2 #include <queue>  3 #include <climits>  4 #include <algorithm>  5 #include <memory.h>  6 #include <stdio.h>  7 using namespace std;  8   9  10 int calSim_1(string s1,int b1,int e1,string s2,int b2,int e2) 11 { 12     if(b1 > e1) 13     { 14         if(b2 > e2) 15         { 16             return 0; 17         } 18         return e2 - b2 + 1; 19     } 20     if(b2 > e2) 21     { 22         if(b1 > e1) 23         { 24             return 0; 25         } 26         return e1 - b1 + 1; 27     } 28     if(s1[b1] == s2[b2]) 29     { 30         return calSim_1(s1,b1+1,e1,s2,b2+1,e2); 31     } 32     else 33     { 34         int len1 = calSim_1(s1,b1,e1,s2,b2+1,e2); 35         int len2 = calSim_1(s1,b1+1,e1,s2,b2,e2); 36         int len3 = calSim_1(s1,b1+1,e1,s2,b2+1,e2); 37  38         len1 = min(len1,len2); 39         len1 = min(len1,len3); 40         return len1+1; 41     } 42 } 43  44 //递归+备忘录版本（DP） 45 int opt[100][100]; 46 int calSim_2(string s1,int b1,int e1,string s2,int b2,int e2) 47 { 48     if(b1 > e1) 49     { 50         if(b2 > e2) 51         { 52             return 0; 53         } 54         return e2 - b2 + 1; 55     } 56     if(b2 > e2) 57     { 58         if(b1 > e1) 59         { 60             return 0; 61         } 62         return e1 - b1 + 1; 63     } 64     if(s1[b1] == s2[b2]) 65     { 66         if(opt[b1+1][b2+1] == -1) 67         { 68             opt[b1+1][b2+1] = calSim_2(s1,b1+1,e1,s2,b2+1,e2); 69         } 70         return opt[b1+1][b2+1]; 71     } 72     else 73     { 74         if(opt[b1][b2+1] == -1) 75         { 76             opt[b1][b2+1] = calSim_2(s1,b1,e1,s2,b2+1,e2); 77         } 78         int len1 = opt[b1][b2+1]; 79         if(opt[b1+1][b2] == -1) 80         { 81             opt[b1+1][b2] = calSim_2(s1,b1+1,e1,s2,b2,e2); 82         } 83         int len2 = opt[b1+1][b2]; 84         if(opt[b1+1][b2+1] == -1) 85         { 86             opt[b1+1][b2+1] = calSim_2(s1,b1+1,e1,s2,b2+1,e2); 87         } 88         int len3 = opt[b1+1][b2+1]; 89  90         len1 = min(len1,len2); 91         len1 = min(len1,len3); 92         return len1+1; 93     } 94 } 95  96 //DP+非备忘录版本 97 int dp[100][100]; 98 int calSim_3(string s1,string s2) 99 {100     int len1 = s1.length();101     int len2 = s2.length();102     int i,j;103     for(i = 0 ; i <= s1.length() ; ++i)104     {105         dp[i][0] = i;106     }107     for(j = 0 ; j <= s2.length() ; ++j)108     {109         dp[0][j] = j;110     }111     for(i = 1 ; i <= s1.length() ; ++i)112     {113         for(j = 1 ; j <= s2.length() ; ++j)114         {115             if(s1[i-1] == s2[j-1])116             {117                 dp[i][j] = dp[i-1][j-1];118             }119             else120             {121                 dp[i][j] = dp[i-1][j] + 1;122                 dp[i][j] = min(dp[i][j],dp[i][j-1]+1);123                 dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);124             }125         }126     }127     return dp[s1.length()][s2.length()];128 }129 130 int main()131 {132     memset(opt,-1,sizeof(opt));133     string s1("abc");134     string s2("ab");135     cout<<calSim_3(s1,s2);136     return 0;137 }

 我的代码里没有加边界情况检查，这一点很重要，不要向我学习，O(∩_∩)O~~


联系
我们