牛客题目——最长公共子序列、矩阵的最小路径和

题目1——最长公共子序列

给定两个字符串str1和str2，输出两个字符串地最长公共子序列。如果最长公共子序列为空，则返回“-1”。目前给出的数据，仅仅会存在一个最长的公共子序列。
要求：空间复杂度 O(n^2)，时间复杂度 O(n^2)。

示例
输入：“1A2C3D4B56”,“B1D23A456A”
输出：“123456”

解题思路

动态规划：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解中得到原问题的解。与分治法不同的是，动态规划分解的子问题往往不是相互独立的，即下一个子问题的求解是建立在上一个子问题的解的基础上，进行下一步求解。

子序列不要求字符连续，只要求相对位置不变。
采用动态规划，具体做法如下：

• 首先处理极端情况，两个字符串中存在空串；
• 定义dp数组来保存子问题的结果，dp[i][j]表示s1中以 i 结尾，s2中以 j 结尾的字符串的最长公共子序列；
• 遍历两个字符串所有位置，若是第 i 位和第 j 位的字符相等，则该问题可以变为1+dp[i-1][j-1]；
• 若是不相等，则当前最长公共子序列应当为dp[i-1][j]和dp[i][j-1]其中最大的那个；
• 因为最后要返回序列，所以我们需要构造一个二维矩阵，二维矩阵中的元素表示当前子问题的解的方向；
• 获取这个序列的时候，应该从表的右下角，根据二维矩阵的记录，不断向上递归添加字符。

代码实现

import java.util.*;
public class Solution {
  
    public String ans(int i,int j,int[][] b,String s){
        String res = "";
        if(i==0 || j==0) return res;
        if(b[i][j] == 1){
            res += ans(i-1,j-1,b,s);
            res += s.charAt(i-1);
        }else if(b[i][j] == 2){
            res += ans(i,j-1,b,s);
        }else if(b[i][j] == 3){
            res += ans(i-1,j,b,s);
        }
        return res;
    }
    public String LCS (String s1, String s2) {
        if(s1.length()==0 || s2.length()==0) return "-1";
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        int[][] b = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = 1+dp[i-1][j-1];
                    b[i][j] = 1;
                }else{
                    if(dp[i][j-1]>dp[i-1][j]){
                        dp[i][j] = dp[i][j-1];
                        b[i][j] = 2;
                    }else{
                        dp[i][j] = dp[i-1][j];
                        b[i][j] = 3;
                    }
                }
            }
        }
        String res = ans(m,n,b,s1);
        if(res.length()==0) return "-1";
        return res ;
    }
}

题目2——矩阵的最小路径和

给定一个n*m的矩阵a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有路径中最小的路径和。
要求：时间复杂度 O(nm)。

示例
输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
输出：12

解题思路

由题意可知，每次只能向下或向右，因次到达右下角的最小路径应该是（i-1,j)和(i,j-1)中的最小路径加上右下角的元素，所以状态转移公式应该为：
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
需要注意的是：要记得初始化dp中第一行和第一列的元素。

代码实现

import java.util.*;
public class Solution {
    public int minPathSum (int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = matrix[0][0];
        for(int i=1;i<m;i++)
            dp[0][i] = dp[0][i-1] + matrix[0][i];
        for(int i=1;i<n;i++)
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + matrix[i][j];
            }
        }
        return dp[n-1][m-1];
    }
}