递归，动态规划实现

描述
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。

注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1\le s\le 150\1≤s≤150
进阶：时间复杂度：O(n^3)\O(n
3
) ，空间复杂度：O(n)\O(n)
输入描述：
输入两个只包含小写字母的字符串

输出描述：
输出一个整数，代表最大公共子串的长度

示例1
输入：
asdfas
werasdfaswer
复制
输出：
6

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String a = in.next();
            String b = in.next();
            int[][] dp = new int[a.length()+1][b.length()+1];
            int max = 0;
            for(int i=1; i<=a.length(); i++){
                for(int j=1; j<=b.length(); j++){
                    // i= 1  j = 1,2,3,4

                    if(a.charAt(i-1) == b.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1] + 1;
                        max = Math.max(dp[i][j], max);
                    }
                }
            }
            System.out.println(max);
        }
        
    }
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

动态规划实现：

  public static int getMax(String s,String  s1){
        int length = 0;
        String shortStr = s.length() > s1.length() ? s1 : s;
        String longStr = s.length() > s1.length() ? s : s1;

        for (int i = 0; i < shortStr.length(); i++) {
            for (int j = shortStr.length(); j > i; j--) {
                if (longStr.contains(shortStr.substring(i, j))) {
                    //保证最长公共子串
                    length = (j - i) > length ? (j - i) : length;
                    continue;
                }

            }

        }




        return length;
    }




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
 public int minPathSum(int[][] grid) {
        int width = grid[0].length, high = grid.length;
        if (high == 0 || width == 0) return 0;
        // 初始化
        for (int i = 1; i < high; i++) grid[i][0] += grid[i - 1][0];
        for (int i = 1; i < width; i++) grid[0][i] += grid[0][i - 1];
        for (int i = 1; i < high; i++)
            for (int j = 1; j < width; j++)
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        return grid[high - 1][width - 1];
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

package com.monkey.od.leetcode;

public class MinPathByGrid {
    static int minPathSum(int[][] grid){
        int width = grid[0].length,high = grid.length;
        if(width == 0 && high == 0) return 0;
        //先考虑两种最简单的情况
        for (int i = 1; i < high; i++)  grid[i][0] += grid[i - 1][0];
        for (int i = 0; i < width; i++) grid[0][i] +=grid[0][i];
        int a = 0;
        //考虑下面的两种情况
        for (int i = 1; i < high; i++) {
            for (int i1 = 1; i1 < width; i1++){
                grid[i][i1] += Math.min(grid[i - 1][i1], grid[i][i1 - 1]);
                a += grid[i][i1];
            }
        }
        return a;
    }

    static int minPathSum2(int[][] grid){
        int x = grid.length;
        int y = grid[0].length;

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if(i == 0 && j == 0){
                    grid[i][j] = grid[0][0];
                }
                else {
                     if(i - 1 >=0 && j - 1 >=0){
                        grid[i][j] +=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
                    }else {
                         //y超出边界
                         if(j - 1 >=0)
                             grid[i][j] = grid[i -1][j] + grid[i][j];
                         //x超出边界
                         else
                             grid[i][j] = grid[i][j-1] + grid[i][j];

                    }
                }



            }
        }
        return grid[x-1][y-1];


    }

    public static int minPathSum1(int[][] grid) {
        int width = grid[0].length, high = grid.length;
        if (high == 0 || width == 0) return 0;
        // 初始化
        for (int i = 1; i < high; i++) grid[i][0] += grid[i - 1][0];
        for (int i = 1; i < width; i++) grid[0][i] += grid[0][i - 1];
        for (int i = 1; i < high; i++)
            for (int j = 1; j < width; j++)
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        return grid[high - 1][width - 1];
    }
    public static void main(String[] args) {
        int[][] a= {
                {},
                {},
                {},


        };
//        int [ ][ ]  arr={{22,15,32,20,18},{12,21,25,19,33},{14,58,34,24,66}};
        int i = minPathSum(a);
        System.out.println(i);
        int i1 = minPathSum1(a);
        System.out.println(i1);


    }
}






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86