刷题DAY16

た入场券 2023-10-14 14:08 51阅读 0赞

## 题目一 ##

给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的最小代价。【举例\]str1="abc",str2=“adc",ic=5,dc=3,rc=2从“abc“编辑成adc",把'b'替换成'd'是代价最小的，所以返回2str1=“abc",str2=“adc“，ic=5,dc=3,rc=100从“abc“编辑成“adc”,先删除”b',然后插入'd'是代价最小的，所以返回8str1=“abc"，str2="abc"，ic=5，dc=3，rc=2不用编辑了，本来就是一样的字符串，所以返回0

dp数组解决

首先先想dp\[i\]\[j\]是是什么意思

i是str1 j是str2 dp\[i\]\[j\]是 str1的前i位 变成 str2的前j位的代价 那也就是左下角出结果呗

那我们看一下每一个位置的依赖

dp\[0\]\[0\] 相同代价就是0 要么代价就是一个替换代价

这里一般情况 应该是 添加+删除>替换 代价的 如果添加+删除的代价比替换的代价还小 那完全可以不需要替换这个操作了 但是这种可能性不能不防啊

dp\[0\]\[j\] 肯定是添加一个的代价

dp\[i\]\[0\] 那肯定是删除i个的代价

然后常态化的呢? dp\[i\]\[j\]

如果i和j位置相同的话 那就直接等于dp\[i-1\]\[j-1\]了 不需要任何新的操作

如果不同 dp\[i-1\]\[j-1\]+一个替换的代价

或者 dp\[i-1\]\[j\]+删除代价

就是先把i-1的给弄立整的

比如 abcdf abcd 它的i-1和j是相同的 所以只要删一个就行了

或者 dp\[i\]\[j-1\]+添加代价

比如 abcd abcdf 那就只要再加一个就行了

> (j-1 i-1 并不能说明j-1一定比i小 这里的含义是位置 也就是说j的前一个位置 和i的当前位置相等 甚至再极端一点 i可能是2 j可能是10呢 ab abcdefghij 它的依赖就走了dp\[2\]\[9\]的值 每个格子只解决相邻的问题就行 虽然这个dp\[2\]\[10\]的这个子问题并不能直接解决这个问题 甚至可以说与原问题(abcdefghi和abcdefghij)毫无干系 但是它作为可以填满整张表的basecase )

我刚开始是这么写的:

public static int MinPath(String str1,String str2,int ic,int dc,int rc) {
               char [] chars1 = str1.toCharArray();
               char [] chars2 = str2.toCharArray();
               int [][] dp = new int [chars1.length][chars2.length]; 
               dp[0][0] = chars1[0]==chars2[0]?0:Math.min(rc,ic+dc);
               for(int i = 1;i<chars1.length;i++) {
            	   dp[i][0] = dp[i-1][0]+dc;
               }
               for(int i = 1;i<chars2.length;i++) {
            	   dp[0][i] = dp[0][i-1]+ic;
               }
               for(int i = 1;i<chars1.length;i++) {
            	   for(int j = 1;j<chars2.length;j++) {
            		   int p1 = dp[i-1][j-1]+rc;
            		   if(chars1[i] == chars2[j]) {
            			   p1 = dp[i-1][j-1];
            		   }
            		   int p2 = Math.min(dp[i-1][j]+dc, dp[i][j-1]+ic);
            		   dp[i][j] = Math.min(p1, p2);
            	   }
               }
               return dp[chars1.length-1][chars2.length-1]; 
    	 }

但是在面对![7dc1ee2632f845dabe8f2801f4a6096c.png][]

例子的时候其实basecase是错的 当dp\[1\]\[2\]的时候 chars1\[1\] chars2\[2\] 相等所以满足 p1 = dp\[i-1\]\[j-1\]; dp\[0\]\[1\] 是什么 a变成fa的最小代价 是先替换一个 再增加一个 这很明显是不对的 我们的最优解应该是 直接加上一个 这种情况是差在哪了呢 差在没考虑当str1为空的时候 比如a f的最佳选择虽然是替换或者删除再添加 那么a->fa的选择 也就被限制在了 先把第一位解决了 再解决后面的

在常态化的时候确实是这个理 但是实际上啊 实际上 我们是忽略掉了 str1a前面的一位 也就是说实际上是可以在a的前面加d 所以实际上我们的dp数组应该大一圈才对

不光是这个原因 还有特殊情况的考虑 如果一个字符串为空呢 对不对 与其搞两个if 不如直接写进dp

har [] chars1 = str1.toCharArray();
               char [] chars2 = str2.toCharArray();
               int [][] dp = new int [chars1.length][chars2.length]; 
               dp[0][0] = chars1[0]==chars2[0]?0:Math.min(rc,ic+dc);
               for(int i = 1;i<chars1.length;i++) {
            	   dp[i][0] = dp[i-1][0]+dc;
               }
               for(int i = 1;i<chars2.length;i++) {
            	   dp[0][i] = dp[0][i-1]+ic;
               }
               for(int i = 1;i<chars1.length;i++) {
            	   for(int j = 1;j<chars2.length;j++) {
            		   int p1 = dp[i-1][j-1]+rc;
            		   if(chars1[i] == chars2[j]) {
            			   p1 = dp[i-1][j-1];
            		   }
            		   int p2 = Math.min(dp[i-1][j]+dc, dp[i][j-1]+ic);
            		   dp[i][j] = Math.min(p1, p2);
            	   }
               }
               return dp[chars1.length-1][chars2.length-1];

另外的 这题每个格子只依赖于 上一个格子或者前一个格子 可以进行优化

而且可以进行 旋转矩阵来保证最优空间(注意转置矩阵后 插入行为和删除行为有变动)

## 题目二 ##

给定两个单词 `word1` 和 `word2` ，返回使得 `word1` 和 `word2`**相同**所需的**最小步数**。

**每步** 可以删除任意一个字符串中的一个字符。

刚开始想的是 能不能a 怎么删都变不了 b 结果人家说 a 和 b 全删没就行

public int minDistance(String word1, String word2) {
             if(word1==word2) {
    			return 0;
    		}
    		if(word1==null) {
    			return word2.length();
    		}
    		if(word1==null) {
    			return word1.length();
    		}
           char [] chars1 = word1.toCharArray();
           char [] chars2 = word2.toCharArray();
           int N = chars1.length;
           int M = chars2.length;
           int [][] dp = new int [N][M];
    				bo
           for(int i = 0;i<N;i++) {
               dp[i][0] = chars1[i] == chars2[0]?i:-1;
           }
           for(int i = 1;i<M;i++) {
           	dp[0][i] = chars1[0] == chars2[i]?i:-1;
           }
          for(int i = 1;i<N;i++) {
       	   for(int j = 1;j<M;j++) {
              	 if(chars1[i]==chars2[j]) {
              		 if(dp[i][j-1]==-1&&dp[i-1][j]==-1) {
              			 dp[i][j] = i+j;
              		 }else {
              			 dp[i][j]=dp[i-1][j-1];
              		 }
              	 }else {
              		 if(dp[i][j-1]==-1&&dp[i-1][j]==-1) {
              			 dp[i][j] = -1;
              		 }else if(dp[i][j-1]==-1||dp[i-1][j]==-1){
              			 dp[i][j]=dp[i][j-1]==-1?dp[i-1][j]+1:dp[i][j-1]+1;
              		 }else {
              			 dp[i][j]=Math.min(dp[i][j-1], dp[i-1][j])+1;
              		}
              	 }
              }
          }
          return dp[N-1][M-1];   
       }

这是刚开始的做法 寄了

public int minDistance2(String word1, String word2) {
          
           char [] chars1 = word1.toCharArray();
           char [] chars2 = word2.toCharArray();
           int N = chars1.length+1;
           int M = chars2.length+1;
           int [][] dp = new int [N][M];
    
           for(int i = 1;i<N;i++) {
               dp[i][0] = i;
           }
           for(int i = 1;i<M;i++) {
        	   dp[0][i] = i;
           }
          for(int i = 1;i<N;i++) {
       	   for(int j = 1;j<M;j++) {
              	 if(chars1[i-1]==chars2[j-1]) {
              		dp[i][j] = dp[i-1][j-1];
              	 }else {
              		dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+1;
              	 }
              }
          }
          return dp[N-1][M-1];   
       }

这个的做法呢 是像上一题一样 多包涵了一圈 也就是加入了字符串为空的可能 所以basecase就有了删除到底的可能性了 然后dp\[i\]\[j\] 如果字符串1的i位置和字符串2的j位置相等 那就不用删了 他就直接等于dp\[i-1\]\[j-1\] 要么不等那就是dp\[i-1\]\[j\]和dp\[i\]\[j-1\]哪个小 再+1 也就是说 这个删除要么是str1删掉一个 要么是str2删掉一个 每次以1为步过 不用不相同时判断dp\[i-1\]\[j-1\]的情况 因为已经包含在dp\[i-1\]\[j\]和dp\[i\]\[j-1\]的判断中了

看人家的题解说是 最长公共子序列 有道理 把最长公共子序列的剩余部分删掉就是结果了

[7dc1ee2632f845dabe8f2801f4a6096c.png]: https://img-blog.csdnimg.cn/7dc1ee2632f845dabe8f2801f4a6096c.png