动态规划（牛客）

题目来自牛客题目库 算法篇面试必刷TOP101。

BM62 斐波那契数列(入门)

题目

略。

解法1 递归

import java.util.*;

public class Solution {

    public int Fibonacci (int n) {
        if(n == 1 || n == 2)
            return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

时间复杂度 O(2^n^), 空间复杂度 O(n)

解法2 动态规划

public class Solution {
    public int Fibonacci(int n) {
        //从0开始，第0项是0，第一项是1
        if(n <= 1)
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         //因n=2时也为1，初始化的时候把a=0，b=1
         for (int i = 2; i <= n; i++){
         //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
}

时间复杂度 O(n), 空间复杂度O(1)

BM63 跳台阶(简单)

题目

题目链接

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40

要求：时间复杂度：O(n) ，空间复杂度：O(1)

示例：

示例1：
输入：2
返回值：2
说明：青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2 
示例2：
输入：7
返回值：21

解法1 记忆化搜索

用数组自下而上计算。

import java.util.*;

public class Solution {

    int[] dp = new int[50];
    public int jumpFloor (int number) {
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= number; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[number];
    }
}

时间复杂度 O(n), 空间复杂度O(n)

解法2 动态规划

对上个解法进一步优化。

import java.util.*;

public class Solution {

    public int jumpFloor (int number) {
        int a = 1, b = 1, c = 1;
        for(int i = 2; i <= number; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

时间复杂度 O(n), 空间复杂度O(1)

BM64 最小花费爬楼梯(简单)

题目

题目链接

给定一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 1≤n≤10^5^ ，数组中的值满足 1≤ cost[i] ≤10^4^

示例：

示例1：
输入：[2,5,20]
返回值：5
说明：你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5 
示例2：
输入：[1,100,1,1,1,90,1,1,80,1]
返回值：6
说明：你将从下标为 0 的台阶开始。
1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6.支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。 

解法 动态规划

import java.util.*;

public class Solution {

    public int minCostClimbingStairs (int[] cost) {
        int[] dp = new int[cost.length + 1];
        for(int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

时间复杂度 O(n), 空间复杂度O(n)

BM65 最长公共子序列(二)(中等)

题目

题目链接

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围：0≤∣str1∣,∣str2∣≤2000

要求：空间复杂度 O(n^2^) ，时间复杂度 O(n^2^)

示例：

示例1：
输入："1A2C3D4B56","B1D23A456A"
返回值："123456"
示例2：
输入："abc","def"
返回值："-1"
示例3：
输入："abc","abc"
返回值："abc"
示例4：
输入："ab",""
返回值："-1"

解法 动态规划、递归

• step 1：优先检查特殊情况。
• step 2：获取最长公共子序列的长度可以使用动态规划，我们以dp[i][j]表示在s1中以i结尾，s2中以j结尾的字符串的最长公共子序列长度。
• step 3：遍历两个字符串的所有位置，开始状态转移：若是i位与j位的字符相等，则该问题可以变成1+dp[i-1][j-1]，即到此处为止最长公共子序列长度由前面的结果加1。
• step 4：若是不相等，说明到此处为止的子串，最后一位不可能同时属于最长公共子序列，毕竟它们都不相同，因此我们考虑换成两个子问题，dp[i-1][j]或者dp[i][j-1]，我们取较大的一个就可以了，由此感觉可以用递归解决。
• step 5：但是递归的复杂度过高，重复计算了很多低层次的部分，因此可以用动态规划，从前往后加，由此形成一个表，表从位置1开始往后相加，正好符合动态规划的转移特征。
• step 6：因为最后要返回该序列，而不是长度，所以在构造表的同时要以另一个二维矩阵记录上面状态转移时选择的方向，我们用1表示来自左上方，2表示来自左边，3表示来自上边。
• step 7：获取这个序列的时候，根据从最后一位开始，根据记录的方向，不断递归往前组装字符，只有来自左上的时候才添加本级字符，因为这种情况是动态规划中两个字符相等的情况，字符相等才可用。

import java.util.*;
public class Solution {
    private String x = "";
    private String y = "";
    //获取最长公共子序列
    String ans(int i, int j, int[][] b){ 
        String res = "";
        //递归终止条件
        if(i == 0 || j == 0)
            return res;
        //根据方向，往前递归，然后添加本级字符
        if(b[i][j] == 1){
            res += ans(i - 1, j - 1, b);
            res += x.charAt(i - 1);
        }
        else if(b[i][j] == 2)
            res += ans(i - 1, j, b);
        else if(b[i][j] == 3)
            res += ans(i,j - 1, b);
        return res;
    }
    
    public String LCS (String s1, String s2) {
        //特殊情况
        if(s1.length() == 0 || s2.length() == 0)
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        // 局部变量赋给类变量，使ans方法可以访问字符串
        x = s1;
        y = s2;
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        //动态规划数组相加的方向
        int[][] b = new int[len1 + 1][len2 + 1];
        //遍历两个字符串每个位置求的最长长度
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                //遇到两个字符相等
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    //考虑由二者都向前一位
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    //来自于左上方
                    b[i][j] = 1;
                }
                //遇到的两个字符不同
                else{
                    //左边的选择更大，即第一个字符串后退一位
                    if(dp[i - 1][j] > dp[i][j - 1]){
                        dp[i][j] = dp[i - 1][j];
                        //来自于左方
                        b[i][j] = 2;
                    }
                    //右边的选择更大，即第二个字符串后退一位
                    else{
                        dp[i][j] = dp[i][j - 1];
                        //来自于上方
                        b[i][j] = 3;
                    }
                }
            }
        }
        //获取答案字符串
        String res = ans(len1, len2, b);
        //检查答案是否位空
        if(res.isEmpty()) 
            return "-1";
        else
            return res;
    }
}

时间复杂度 O(n^2^), 空间复杂度O(n^2^)

BM66 最长公共子串(中等)

题目

题目链接

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

数据范围： 1≤∣str1∣,∣str2∣≤5000

要求： 时间复杂度 O(n^2^), 空间复杂度O(n^2^)

示例：

输入："1AB2345CD","12345EF"
返回值："2345"

注：本题求“最长公共子串”，注意和上题求“最长公共子序列”区分。

解法 动态规划

import java.util.*;
public class Solution {
    public String LCS (String str1, String str2) {
        //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; 
        int max = 0;
        int pos = 0;
        for(int i = 1; i <= str1.length(); i++){
            for(int j = 1; j <= str2.length(); j++){
                //如果该两位相同
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) 
                    //则增加长度
                    dp[i][j] = dp[i - 1][j - 1] + 1; 
                else 
                    //该位置为0
                    dp[i][j] = 0; 
                //更新最大长度
                if(dp[i][j] > max){ 
                    max = dp[i][j];
                    pos = i;
                }
            }
        }
        return str1.substring(pos - max, pos);
    }
}

时间复杂度 O(n^2^), 空间复杂度O(n^2^)

BM67 不同路径的数目(一)(简单)

题目

题目链接

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：0<n,m≤100，保证计算结果在32位整型范围内

要求：空间复杂度 O(n*m)，时间复杂度 O(n*m)

进阶：空间复杂度 O(1)，时间复杂度 O(min(m, n))

示例：

示例1：
输入：2,1
返回值：1
示例2：
输入：2,2
返回值：2

解法1 递归

• step 1：（终止条件） 当矩阵变长n减少到1的时候，很明显只能往下走，没有别的选择了，只有1条路径；同理m减少到1时也是如此。因此此时返回数量为1.
• step 2：（返回值） 对于每一级都将其两个子问题返回的结果相加返回给上一级。
• step 3：（本级任务） 每一级都有向下或者向右两种路径选择，分别进入相应分支的子问题。

import java.util.*;
public class Solution {
    public int uniquePaths (int m, int n) {
        //矩阵只要有一条边为1，路径数就只有一种了
        if(m == 1 || n == 1) 
            return 1;
        //两个分支
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); 
    }
}

空间复杂度 O(n+m)，时间复杂度 O(n*m)

解法2 动态规划

• step 1：用dp[i][j]表示大小为i*j的矩阵的路径数量，下标从1开始。
• step 2：（初始条件） 当i或者j为1的时候，代表矩阵只有一行或者一列，因此只有一种路径。
• step 3：（转移方程） 每个格子的路径数只会来自它左边的格子数和上边的格子数，因此状态转移为dp[i][j] = dp[i-1][j] + dp[i][j-1]

import java.util.*;

public class Solution {

    public int uniquePaths (int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 || j == 1)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }
}

空间复杂度 O(n*m)，时间复杂度 O(n*m)

BM68 矩阵的最小路径和(中等)

题目

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

数据范围: 1≤n,m≤500，矩阵中任意值都满足 0≤a~i,j~≤100

要求：时间复杂度 O(n*m)

例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，

所选择的最小累加和路径如下图所示：

示例：

示例1：
输入：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值：12
示例2：
输入：[[1,2,3],[1,2,3]]
返回值：7

解法 动态规划

import java.util.*;
public class Solution {
    public int minPathSum (int[][] matrix) {
        int n = matrix.length;
        //因为n,m均大于等于1
        int m = matrix[0].length;  
        //dp[i][j]表示以当前i，j位置为终点的最短路径长度
        int[][] dp = new int[n][m];
        dp[0][0] = matrix[0][0];
        //处理第一列
        for(int i = 1; i < n; i++)
            dp[i][0] = matrix[i][0] + dp[i - 1][0];
        //处理第一行
        for(int j = 1; j < m; j++)
            dp[0][j] = matrix[0][j] + dp[0][j - 1];
        //其他按照公式来
        for(int i = 1; i < n; i++){ 
          for(int j = 1; j < m; j++){
              dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
          }
      }
       return dp[n - 1][m - 1];
    }
}

BM69 把数字翻译成字符串(中等)

题目

有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。

现在给一串数字，返回有多少种可能的译码结果

数据范围：字符串长度满足 0<n≤90

进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例：

示例1：
输入："12"
返回值：2
说明：2种可能的译码结果（”ab” 或”l”）
示例2：
输入："31717126241541717"
返回值：192
说明：192种可能的译码结果 

解法 动态规划

import java.util.*;
public class Solution {
    public int solve (String nums) {
        //排除0
        if(nums.equals("0"))  
            return 0;
        //排除只有一种可能的10 和 20
        if(nums == "10" || nums == "20")  
            return 1;
        //当0的前面不是1或2时，无法译码，0种
        for(int i = 1; i < nums.length(); i++){  
            if(nums.charAt(i) == '0')
                if(nums.charAt(i - 1) != '1' && nums.charAt(i - 1) != '2')
                    return 0;
        }
        int[] dp = new int[nums.length() + 1];
        //辅助数组初始化为1
        Arrays.fill(dp, 1);  
        for(int i = 2; i <= nums.length(); i++){
            //在11-19，21-26之间的情况
            if((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' && nums.charAt(i - 1) < '7'))
               dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
}

BM70 兑换零钱(一)(中等)

题目

题目链接

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

数据范围：数组大小满足 0≤n≤10000 ， 数组中每个数字都满足 0<val≤10000，0≤aim≤5000

要求：时间复杂度 O(n*aim) ，空间复杂度 O(aim)。

示例：

示例1：
输入：[5,2,3],20
返回值：4
示例2：
输入：[5,2,3],0
返回值：0
示例3：
输入：[3,5],2
返回值：-1

解法 动态规划

import java.util.*;
public class Solution {
    public int minMoney (int[] arr, int aim) {
        //小于1的都返回0
        if(aim < 1) 
            return 0;
        int[] dp = new int[aim + 1];
        //dp[i]表示凑齐i元最少需要多少货币数
        Arrays.fill(dp, aim + 1); 
        dp[0] = 0; 
        //遍历1~aim元
        for(int i = 1; i <= aim; i++){ 
            //每种面值的货币都要枚举
            for(int j = 0; j < arr.length; j++){ 
                //如果面值不超过要凑的钱才能用
                if(arr[j] <= i) 
                    //维护最小值
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1); 
            }
        }
        //如果最终答案大于aim代表无解
        return dp[aim] > aim ? -1 : dp[aim]; 
    }
}

时间复杂度 O(n*aim) ，空间复杂度 O(aim)。

BM71 最长上升子序列(一)(中等)

题目

题目链接

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 i<j 且 arr~i~≥ arr~j~

数据范围： 0≤n≤1000

要求：时间复杂度 O(n^2^)， 空间复杂度 O(n)

示例：

输入：[6,3,1,5,2,3,7]
返回值：4
说明：该数组最长上升子序列为 [1,2,3,7] ，长度为4

解法 动态规划

• step 1：用dp[i]表示到元素i结尾时，最长的子序列的长度，初始化为1，因为只有数组有元素，至少有一个算是递增。
• step 2：第一层遍历数组每个位置，得到n个长度的子数组。
• step 3：第二层遍历相应子数组求对应到元素i结尾时的最长递增序列长度，期间维护最大值。
• step 4：对于每一个到i结尾的子数组，如果遍历过程中遇到元素j小于结尾元素，说明以该元素结尾的子序列加上子数组末尾元素也是严格递增的，因此转移方程为dp[i] = dp[j] + 1。

import java.util.*;
public class Solution {
    public int LIS (int[] arr) {
        if(arr.length == 0)
            return 0;
        int[] dp = new int[arr.length];
        //设置数组长度大小的动态规划辅助数组
        Arrays.fill(dp, 1); 
        int res = 1;
        for(int i = 1; i < arr.length; i++){
            for(int j = 0; j < i; j++){
                //可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1){
                    //i点比j点大，理论上dp要加1
                    dp[i] = dp[j] + 1; 
                    //找到最大长度
                    res = Math.max(res, dp[i]); 
                }
            }
        }
        return res;
    }
}

BM72 连续子数组的最大和(简单)

题目

题目链接

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

1<=n<=2×10^5^

−100<=a[i]<=100

要求:时间复杂度为 O(n)，空间复杂度为 O(n)

进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

示例：

示例1：
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
示例2：
输入：[2]
返回值：2
示例3：
输入：[-10]
返回值：-10

解法1 动态规划

public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        int max = array[0];
        dp[0] = array[0];
        for(int i = 1; i < array.length; i++){
            // 动态规划，状态转移方程，确定dp[i]的最大值
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max,dp[i]);
        }
        return max;
    }

时间复杂度为 O(n)，空间复杂度为 O(n)

解法2 动态规划

public int FindGreatestSumOfSubArray(int[] array) {
        int sum = 0;
        int max = array[0];
        for(int i = 0; i < array.length; i++){
            // 优化动态规划，确定sum的最大值
            sum = Math.max(sum + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max,sum);
        }
        return max;
}

时间复杂度为 O(n)，空间复杂度为 O(1)

BM73 最长回文子串(中等)

题目

题目链接

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

数据范围： 1≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n^2^)

进阶: 空间复杂度 O(n)，时间复杂度 O(n)

示例：

示例1：
输入："ababc"
返回值：3
说明：最长的回文子串为"aba"与"bab"，长度都为3
示例2：
输入："abbba"
返回值：5
示例3：
输入："b"
返回值：1

解法1 中心扩展

import java.util.*;
public class Solution {
    public int fun(String s, int begin, int end){
        //每个中心点开始扩展
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){ 
            begin--;
            end++;
        }
        //返回长度
        return end - begin - 1; 
    } 
    public int getLongestPalindrome (String A) {
        int maxlen = 1;
        //以每个点为中心
        for(int i = 0; i < A.length() - 1; i++) 
            //分奇数长度和偶数长度向两边扩展
            maxlen = Math.max(maxlen, Math.max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
}

空间复杂度 O(1)，时间复杂度 O(n^2^)

解法2 manacher算法（动态规划）（没看懂）

BM74 数字字符串转化成IP地址(中等)

题目

题目链接

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为”25525522135”,

返回[“255.255.22.135”, “255.255.221.35”]. (顺序没有关系)

数据范围：字符串长度 0≤n≤12

要求：空间复杂度 O(n!),时间复杂度 O(n!)

注意：ip地址是由四段数字组成的数字序列，格式如 “x.x.x.x”，其中 x 的范围应当是 [0,255]。

示例：

示例1：
输入："25525522135"
返回值：["255.255.22.135","255.255.221.35"]
示例2：
输入："1111"
返回值：["1.1.1.1"]
示例3：
输入："000256"
返回值：[]

解法

枚举三个点的位置。

import java.util.*;
public class Solution {
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<String>();
        int n = s.length();
        //遍历IP的点可能的位置（第一个点）
        for(int i = 1; i < 4 && i < n - 2; i++){ 
            //第二个点的位置
            for(int j = i + 1; j < i + 4 && j < n - 1; j++){ 
                //第三个点的位置
                for(int k = j + 1; k < j + 4 && k < n; k++){ 
                    //最后一段剩余数字不能超过3
                    if(n - k >= 4) 
                        continue; 
                    //从点的位置分段截取，substring(a, b)方法获取范围[a, b)
                    String a = s.substring(0, i);
                    String b = s.substring(i, j);
                    String c = s.substring(j, k);
                    String d = s.substring(k);
                    //IP每个数字不大于255，parseInt()方法将字符串转为整型
                    if(Integer.parseInt(a) > 255 || Integer.parseInt(b) > 255 || Integer.parseInt(c) > 255 || Integer.parseInt(d) > 255)
                        continue;
                    //排除前导0的情况
                    if((a.length() != 1 && a.charAt(0) == '0') || (b.length() != 1 && b.charAt(0) == '0') ||  (c.length() != 1 && c.charAt(0) == '0') || (d.length() != 1 && d.charAt(0) == '0'))
                        continue;
                    //组装IP地址
                    String temp = a + "." + b + "." + c + "." + d; 
                    res.add(temp);
                }
            }
        }
        return res;
    }
}

BM75 编辑距离(一)(较难)

题目

题目链接

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。

你可以对字符串进行3种操作：

1.插入一个字符

2.删除一个字符

3.修改一个字符。

字符串长度满足 1≤n≤1000 ，保证字符串中只出现小写英文字母。

示例：

示例1：
输入："nowcoder","new"
返回值：6
说明：
"nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次
"nowcoder"=>"new"(删除"coder")，删除操作5次   
示例2：
输入："intention","execution"
返回值：5
说明：一种方案为:
因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改即可  

解法 动态规划

把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转移，那可以考虑动态规划。用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离，那很明显dp[str1.length][str2.length]就是我们要求的编辑距离。（下标从1开始）

import java.util.*;
public class Solution {
    public int editDistance (String str1, String str2) {
        int n1 = str1.length();
        int n2 = str2.length();
        //dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
        int[][] dp = new int[n1 + 1][n2 + 1]; 
        //初始化边界
        for(int i = 1; i <= n1; i++) 
            dp[i][0] = dp[i - 1][0] + 1;
        for(int i = 1; i <= n2; i++)
            dp[0][i] = dp[0][i - 1] + 1;
        //遍历第一个字符串的每个位置
        for(int i = 1; i <= n1; i++) 
            //对应第二个字符串每个位置
            for(int j = 1; j <= n2; j++){ 
                //若是字符相同，此处不用编辑
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) 
                    //直接等于二者前一个的距离
                    dp[i][j] = dp[i - 1][j - 1]; 
                else
                    //选取增加1位、添加1位、减少1位中最小的距离，加上此处编辑距离1
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; 
            }
        return dp[n1][n2]; 
    }
}

BM76 正则表达式匹配(较难)

题目

题目链接

请实现一个函数用来匹配包括’.’和’*‘的正则表达式。

1.模式中的字符’.’表示任意一个字符

2.模式中的字符’*‘表示它前面的字符可以出现任意次（包含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

数据范围:

1. str 只包含从 a-z 的小写字母。

2. pattern 只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘‘。

3. 0≤str.length≤26
4. 0≤pattern.length≤26

示例：

示例1：
输入："aaa","a*a"
返回值：true
说明：中间的*可以出现任意次的a，所以可以出现1次a，能匹配上 
示例2：
输入："aad","c*a*d"
返回值：true
说明：因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。 
示例3：
输入："a",".*"
返回值：true
说明：".*" 表示可匹配零个或多个（'*'）任意字符（'.'） 
示例4：
输入："aaab","a*a*a*c"
返回值：false

解法 动态规划（似懂非懂，以后再看）

BM77 最长的括号子串(较难)

题目

题目链接

给出一个长度为 n 的，仅包含字符 ‘(‘ 和 ‘)’ 的字符串，计算最长的格式正确的括号子串的长度。

例1: 对于字符串 “(()” 来说，最长的格式正确的子串是 “()” ，长度为 2 .

例2：对于字符串 “)()())” , 来说, 最长的格式正确的子串是 “()()” ，长度为 4 .

字符串长度：0≤n≤ 5∗10^5^

要求时间复杂度 O(n) ,空间复杂度 O(n)

示例：

示例1：
输入："(()"
返回值：2
示例2：
输入："(())"
返回值：4

解法1 栈

• step 1：可以使用栈来记录左括号下标。
• step 2：遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。
• step 3：然后长度则更新为当前下标与栈顶下标的距离。
• step 4：遇到不符合的括号，可能会使栈为空，因此需要使用start记录上一次结束的位置，这样用当前下标减去start即可获取长度，即得到子串。
• step 5：循环中最后维护子串长度最大值。

import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++){
            //左括号的下标入栈
            if(s.charAt(i) == '(') 
                st.push(i);
            //右括号
            else{ 
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.isEmpty()) 
                    start = i;
                else{
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = Math.max(res, i - st.peek());
                    //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else 
                        res = Math.max(res, i - start);
                }
            }
        }
        return res;
    }
}

解法2 动态规划(看晕了)

BM78 打家劫舍(一)(中等)

题目

题目链接

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。

给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

数据范围：数组长度满足 1≤n≤2×10^5^ ，数组中每个值满足 1≤num[i]≤5000

示例：

示例1：
输入：[1,2,3,4]
返回值：6
说明：最优方案是偷第 2，4 个房间  
示例2：
输入：[1,3,6]
返回值：7
说明：最优方案是偷第 1，3个房间 
示例3：
输入：[2,10,5]
返回值：10
说明：最优方案是偷第 2 个房间  

解法 动态规划

import java.util.*;
public class Solution {
    public int rob (int[] nums) {
        //dp[i]表示长度为i的数组，最多能偷取多少钱
        int[] dp = new int[nums.length + 1]; 
        //长度为1只能偷第一家
        dp[1] = nums[0]; 
        for(int i = 2; i <= nums.length; i++)
            //对于每家可以选择偷或者不偷
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        return dp[nums.length];
    }
}

BM79 打家劫舍(二)(中等)

题目

题目链接

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

数据范围：数组长度满足 1≤n≤2×10^5^ ，数组中每个值满足 1≤nums[i]≤5000

示例：

示例1：
输入：[1,2,3,4]
返回值：6
说明：最优方案是偷第 2 4 个房间
示例2：
输入：[1,3,6]
返回值：6
说明：由于 1 和 3 是相邻的，因此最优方案是偷第 3 个房间  

解法 动态规划

分类讨论：偷第一家，不偷最后一家；偷最后一家，不偷第一家。

import java.util.*;
public class Solution {
    public int rob (int[] nums) {
        //dp[i]表示长度为i的数组，最多能偷取多少钱
        int[] dp = new int[nums.length + 1]; 
        //选择偷了第一家
        dp[1] = nums[0]; 
        //最后一家不能偷
        for(int i = 2; i < nums.length; i++) 
            //对于每家可以选择偷或者不偷
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        int res = dp[nums.length - 1]; 
        //清除dp数组，第二次循环
        Arrays.fill(dp, 0); 
        //不偷第一家
        dp[1] = 0; 
        //可以偷最后一家
        for(int i = 2; i <= nums.length; i++) 
            //对于每家可以选择偷或者不偷
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]); 
        //选择最大值
        return Math.max(res, dp[nums.length]); 
    }
}

BM80 买卖股票的最好时机(一)(简单)

题目

题目链接

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

数据范围： 0≤n≤10^5^,0≤val≤10^4^

要求：空间复杂度 O(1)，时间复杂度 O(n)

示例：

示例1：
输入：[8,9,2,5,4,7,1]
返回值：5
说明：在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
示例2：
输入：[2,4,1]
返回值：2
示例3：
输入：[3,2,1]
返回值：0

解法1 动态规划

• step 1：用 dp[i][0]表示第i天不持股到该天为止的最大收益， dp[i][1]表示第i天持股，到该天为止的最大收益。
• step 2：（初始状态） 第一天不持股，则总收益为0，dp[0][0] = 0; ；第一天持股，则总收益为买股票的花费，此时为负数，dp[0][1] = -prices[0]。
• step 3：（状态转移） 对于之后的每一天，如果当天不持股，有可能是前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同，也有可能是当天才卖掉，我们选择较大的状态 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])；
• step 4：如果当天持股，有可能是前面若干天中买了股票，当天还没卖，因此收益与前一天相同，也有可能是当天买入，此时收益为负的股价，同样是选取最大值：dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int n = prices.length;
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2]; 
        //第一天不持股，总收益为0
        dp[0][0] = 0; 
        //第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0]; 
        //遍历后续每天，状态转移
        for(int i = 1; i < n; i++){ 
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0]; 
    }
}

空间复杂度 O(n)，时间复杂度 O(n)

解法2 贪心

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        //维护最大收益
        int res = 0; 
        //排除特殊情况
        if(prices.length == 0) 
            return res;
        //维护最低股票价格
        int Min = prices[0]; 
        //遍历后续股票价格
        for(int i = 1; i < prices.length; i++){ 
            //如果当日价格更低则更新最低价格
            Min = Math.min(Min, prices[i]); 
            //维护最大值
            res = Math.max(res, prices[i] - Min); 
        }
        return res;
    }
}

空间复杂度 O(1)，时间复杂度 O(n)

BM81 买卖股票的最好时机(二)(中等)

题目

题目链接

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票

2. 如果不能获取收益，请返回0

3. 假设买入卖出均无手续费

数据范围： 1≤n≤1×10^5^ ， 1≤prices[i]≤10^4^

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例：

示例1：
输入：[8,9,2,5,4,7,1]
返回值：7
说明：
在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7  
示例2：
输入：[5,4,3,2,1]
返回值：0
说明：由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。  
示例3：
输入：[1,2,3,4,5]
返回值：4
说明：第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。  

解法1 动态规划

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int n = prices.length;
        //dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        int[][] dp = new int[n][2]; 
        //第一天不持股，总收益为0
        dp[0][0] = 0; 
        //第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0]; 
        //遍历后续每天，状态转移
        for(int i = 1; i < n; i++){ 
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        //最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0]; 
    }
}

解法2 贪心

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int res = 0;
        for(int i = 1; i < prices.length; i++){
            //只要某段在递增就有收益
            if(prices[i - 1] < prices[i]) 
                //收益累加
                res += prices[i] - prices[i - 1]; 
        }
        return res;
    }
}

BM82 买卖股票的最好时机(三)(较难)

题目

题目链接

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

数据范围：1≤n≤10^5^，股票的价格满足 1≤val≤10^4^

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例：

示例1：
输入：[8,9,3,5,1,3]
返回值：4
说明：
第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。    
示例2：
输入：[9,8,4,1]
返回值：0
示例3：
输入：[1,2,8,3,8]
返回值：12
说明：第一笔股票交易在第一天买进，第三天卖出；第二笔股票交易在第四天买进，第五天卖出；总收益为12。
因最多只可以同时持有一只股票，所以不能在第一天进行第一笔股票交易的买进操作，又在第二天进行第二笔股票交易的买进操作（此时第一笔股票交易还没卖出），最后两笔股票交易同时在第三天卖出，也即以上操作不满足题目要求。  

解法 动态规划

• dp[i][0] 表示到第i天为止没有买过股票的最大收益
• dp[i][1] 表示到第i天为止买过一次股票还没有卖出的最大收益
• dp[i][2] 表示到第i天为止买过一次也卖出过一次股票的最大收益
• dp[i][3] 表示到第i天为止买过两次只卖出过一次股票的最大收益
• dp[i][4] 表示到第i天为止买过两次同时也买出过两次股票的最大收益

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][5];
        //初始化dp为最小
        Arrays.fill(dp[0], -10000); 
        //第0天不持有状态
        dp[0][0] = 0; 
        //第0天持有股票
        dp[0][1] = -prices[0]; 
        //状态转移
        for(int i = 1; i < n; i++){ 
            dp[i][0] = dp[i - 1][0]; 
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        //选取最大值，可以只操作一次
        return Math.max(dp[n - 1][2],Math.max(0, dp[n - 1][4])); 
    }
}

空间复杂度 O(n)，时间复杂度 O(n)

总结

• 动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

• 动态规划的过程：
  • 确定初始状态
  • 状态转移
• 动态规划的dp数组的下标可能与题目所给的数组下标不对应，要仔细确认下标。
• 与自己和解：困难的动态规划难度很大，企业笔试一般不会考，看不懂可以原谅自己。