刷题-DAY6

谁借莪１个温暖的怀抱￠ 2023-10-13 18:36 13阅读 0赞

## 第一题 ##

给定一个二维数组matrix，其中每个数都是正数，要求从左上到右下每一步只能向右或者向下，沿途经过的数字要累加起来最后请返回最小的路径和

动态规划的空间压缩技巧！

首先还是建一个dp\[\]\[\]数组

dp\[i\]\[j\] 依赖于左侧dp\[i-1\]\[j\] 和 上侧dp\[i\]\[j-1\] 加上本身权重 中的更小值

basecase 是i = 0时 和 j=0时 只有自身的权重

既然dp\[i\]\[j\] 只依赖 上一行 和本行前一个格子 所以我们可以采用空间压缩技巧 只需要一行就足够了

但是呢 我们要考虑一种情况 就是一行 100000列的情况 这种情况压缩成1行并没有什么实际意义

但是呢 我们要是 一列 100000行 是不是就很带劲了 很省空间了 所以我们压缩的时候要选择行和列中更小的 进行压缩

public static int MinKth(int [][] arr) {
    		if (arr == null || arr.length == 0 || arr[0] == null || arr[0].length == 0) {
    			return 0;
    		}
            int Max = Math.max(arr.length,arr[0].length);
            int Min = Math.min(arr.length,arr[0].length);
            boolean Isreverse = (Max == arr[0].length);//是否翻转 如果行更长就翻转了 
            int[] dp = new int[Min];
    		dp[0] = arr[0][0];
    		for (int i = 1; i < Min; i++) {
    			dp[i] = dp[i - 1] + (Isreverse ? arr[i][0] : arr[0][i]);
    		}
    	    for(int i = 1;i<Max;i++) {
    	    	dp[0] = dp[0] + (Isreverse ? arr[0][i] : arr[i][0]);
    	    	for(int j = 1;j<Min;j++) {
    	    		dp[j] = Math.min(dp[j-1], dp[j]) + (Isreverse ? arr[j][i] : arr[i][j]);
    	    	}
    	    }
    	    return dp[dp.length-1];
    	}

再来一道?

## 题目二 ##

求以str1为主串str2子串最长公共子字符串

啊 区分子字符串和子序列 子序列不一定要连着 子字符串一定要连着

经典动态规划

dp\[i\]\[j\] 位置是 以str1 i位置结尾 和 str2 j位置结尾的 公共子字符串有多长

首先 如果str\[i\]和str\[j\]不相等 一定为0 公共子串怎么可能结尾不同

这个位置依赖于

i-1 j-1位置的公共子字符串 如果i == j 的话 那么当前位置就是 dp\[i-1\]\[j-1\]+1 不同的话 那就是0

例如 abcd e 和 abcd f 这个e f位置就是i j位置

我刚开始没理解 dp\[i\]\[j-1\] 是什么意思 什么是以str1 i位置结尾 str2 j-1位置结尾 这种情况就是对应

fabcd abcd i=5 j-1=4 对吧 字符串最长的可能性是在这种情况出现的 这种情况 依赖于什么呢

也依赖于str1 str2各向前推一个

所以说dp数组是这样的 每一个位置都依赖于它的左上角 当当前位置i j字符相等时 当前位置答案为

dp\[i-1\]\[j-1\]+1 如果不相等为0

public static int MaxStr(String str1,String str2) {
    		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
    			return 0;
    		}
    	       char [] chars1 = str1.toCharArray();
    	       char [] chars2 = str2.toCharArray();
    	       int N = chars2.length;
    	       int M = chars1.length;
    	       int [][] dp  = new int [N][M];
    	       for(int i = 0;i<M;i++) {
    	    	dp[0][i] = chars1[i] == chars2[0] ? 1:0;
    	       }
    	       for(int i = 0;i<N;i++) {
    	    	   dp[i][0] = chars1[0] == chars2[i] ? 1:0;
    	       }
    	       int max = 0;
    	       for(int i = 1;i<N;i++) {
    	    	   for(int j = 1;j<M;j++) {
    	    		   dp[i][j] = dp[i-1][j-1]+ (chars1[j]==chars2[i]?1:0);
    	    		   max = Math.max(max, dp[i][j]);
    	    	   }
    	       }
    	       return max;
    	}

所以说 有两点 1.二维数组的数据筛选

if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) \{  
return 0;  
\}

2.二维数组的两个参数 不是横坐标和纵坐标 是在第几行(纵坐标)第几列(横坐标)

本质上来讲就是将str1 str2的子字符串相比较 那假如说str1子字符串为abcd str2为abc 此时最大子字符串应该长度为3啊 那为什么在我们的dp数组中结果为0呢 因为我们已经通过max抓过了 abc(abcd的子字符串) 和 abc 结果为3 此时的abcd和abc的答案只是为了推下一个格子而准备的

所以要求一定以最后一个字符结尾

但如果说真的是以str1 str2的每个子字符串比较 那么 sdabcef 和 ggabcge 这两个中间的abc是什么时候比较的呢 答案是sdabc 和ggabc的时候已经比过了 所以含义不正确

正确含义是 我用str\[1\]的零位置 去挨个和str2的每个字符相比 如果相同 答案就为1 且接着比对下一个字符 动态规划的本质就是加速重复计算项 所以明知道后面已经不同了 还是要比对直到最后 这会减少重复计算

趁热打铁

## 第三题 ##

最长公共子序列问题

还是给两个字符串 str1 str2 求最长公共子序列

子序列就不一定连着了

还是dp数组

dp\[i\]\[j\]的意义还是 str1\[0....i\] 与 str2\[0......j\]的最长公共子序列长度是多少 本质上还是穷举每种可能 但是有dp数组加速

这题当i j 位置字符不同的话 还直接等于0吗 并不 公共子序列不要求连着

这次的动态规划思想为

dp\[i\]\[j\]

如果最长子序列与j 无关则依赖dp\[i\]\[j-1\]

例:afcd gcdg

最长公共子序列与g位置无关 当前最长公共子序列和i 及 i-1位置最长子序列相同

如果最长子序列与i 无关则依赖dp\[i-1\]\[j\]

例abcd afbc

那么此位置答案与dp\[i-1\]\[j\]相等

如果最长子序列与i j都无关

那就依赖与dp\[i-1\]\[j-1\]

如果与i j都有关那会(只在i==j时出现)

dp\[i\]\[j\] = dp\[i\]\[j\]+1

然后这四种情况取最大值 啊 你想啊 这四种情况肯定只能出现一个吧 如果这四种情况中的某一种获得了最大的答案 说明这种情况发生了 举个例子

afcd gcdg 的dp\[i\]\[j-1\] 答案为2 dp\[i-1\]\[j\]的答案为1 dp\[i-1\]\[j-1\]位置答案为1

这次的本质是 判断每个字符要与不要 本质上和上一题大体相同 只不过子序列不一定相邻 即使断了也不归0

public static int MaxStr(String text1,String text2) {
    		if (text1 == null || text2 == null || text1.equals("") || text2.equals("")) {
    			return 0;
    		}
    	       char [] chars1 = text1.toCharArray();
    	       char [] chars2 = text2.toCharArray();
    	       int N = chars1.length;
    	       int M = chars2.length;
    	       int [][] dp  = new int [N][M];
    	       for(int i = 0;i<M;i++) {
    	    	dp[0][i] = chars1[0] == chars2[i] ? 1:0;
    	       }
    	       for(int i = 0;i<N;i++) {
    	    	   dp[i][0] = chars1[i] == chars2[0] ? 1:0;
    	       }
    	       for(int i = 1;i<N;i++) {
    	    	   for(int j = 1;j<M;j++) {
    	    		   int max = Math.max(dp[i-1][j], chars1[i]==chars2[j]?dp[i-1][j-1]+1:0);
    	    		   dp[i][j] = Math.max(dp[i][j-1],max);
    	    		   //为什么闭口不谈dp[i-1][j-1]呢 如果chars1[i]==chars2[j] dp[i-1][j-1]+1肯定大于dp[i-1][j-1]
    	    		   //如果chars1[i]!=chars2[j] dp[i-1][j]怎么来的 比dp[i-2][j] dp[i-1][j-1] dp[i][j-1]呢?比dp[i-1][j-1] dp[i][j-2]
    	    		   //所以早就比过了 还比了两次
    	    		   
    	    	   }
    	       }
    	       return dp[N-1][M-1];