算法笔记（Java）——动态规划

动态规划方法论

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
动规和递归的区别是动规不是暴力的，产生的中间结果用数组记录起来，比较高效，详情可以看文章：

教你入门动态规划

动态规划的解题步骤：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组（当出现问题时用此方法调试）

动态规划常见题型：

1. 背包问题：难点在遍历顺序那里，01背包和完全背包 排列组合问题等等的遍历顺序
2. 子序列问题：难点在思考出dp数组的含义，甚至很可能都看不出要用dp来做
3. 股票问题：难点在理解状态有几种，dp数组能否表示所有状态吗，持有和卖出的区别
4. 打家劫舍：不太难好像

个人觉得最难理解的就是遍历顺序，甚至比确定递推公式还难，如果迷糊了可以手写dp数组来理解，请注意一维和二维还是有点不一样的，可以都试试。

简单示例：

70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n<=2){
            return n;
        }
        int[] count = new int[n+1]; // 1.dp[i]： 爬到第i层楼梯，有dp[i]种方法
        count[1] = 1;
        count[2] = 2;
        for(int i=3;i<=n;i++){
            count[i] = count[i-1]+count[i-2]; // 2.dp[i] = dp[i - 1] + dp[i - 2] 
        }
        return count[n];
    }
}

背包问题

01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
01背包和完全背包的区别就是物品只能放一次
例如：

物品为：
物品 重量 价值
物品0 1 15
物品1 3 20
物品2 4 30
问背包能背的物品最大价值是多少？

二维dp数组

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

含义是：
遍历到物品i的时候，背包容量为j的最大价值分为放i和不放i两种情况 dp[i-1][j]为不放i，dp[i - 1][j - weight[i]] + value[i])为放i
遍历顺序都可以，可以先遍历背包再遍历物品，也可以先遍历物品再遍历背包。因为根据递推公式，求当前dp值是用的上一行的元素或者左上的元素，因此从左到右和从上到下两种方式均可。

初始化：要初始化第一行，因为递推公式有i-1。

推导dp数组

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}

一维dp数组

从二维dp数组可知，确定当前dp值只需要上面或者左上的元素，那么可以使用滚动数组的方式，只使用一个一维数组。

1. 在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2. 递推公式：dp[j]是不选 后面那个是选，对应二维的上面的元素和左上的元素

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 无需初始化
4. 遍历顺序：跟二维不一样，先遍历物品，再方向遍历背包。反向是避免覆盖，因为如果左面的dp值更新了以后，对应二维情况是同一行左面的值，而不是上一行最面的值，会重复选取，需要重复选取的完全背包才可以正向遍历
5. 打印dp数组

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

PS：之前一直认为，为什么一维情况可以直接从右向左遍历呢，右边的dp[j]难道不需要左边的值吗，后来发现确实不需要，只需要上一行同列的值和上一行左边的值，可以打印数组进行尝试理解，注意是01背包，物品只能放进去一次。

背包问题在题目中并不明显，需要自己抽象出题目的特点来：

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

乍一看看不出来是个背包问题，但是要想分割成等和子集，一定有两部分的和要相等的，而且两部分的和为sum的一半，所以可以往容量为 sum/2的背包里装物品，看看能不能装满：

class Solution {
    public boolean canPartition(int[] nums) {
    // 背包问题的解决公式：二维 dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i]]+nums[i]
        // 一维：dp[j] = dp[j]+dp[j-nums[i]]+nums[i]
        // 1.确定dp数组和下标的含义
        // 2.确定递推公式
        // 3.确定初始化方式
        // 4.确定遍历顺序 打印验证
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            
            sum+=nums[i];
        }
       
        if(sum%2!=0){
            return false;
        }
         int half = sum/2;

         int[] dp = new int[half+1];
        for(int i=1;i<nums.length;i++){
            for(int j=half;j>0;j--){
                if(j>=nums[i])
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[half] == half){
            return true;
        } else {
            return false;
        }

    }
}

01背包组合问题

如果让你求的是一个组合的情况怎么办，比如：

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

首先你得看出来这个题可以转化为背包问题：
假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target -> x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法

这次是让求满足要求的组合数，使用一维dp数组解决：

1. dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
2. dp[j] += dp[j - nums[i]]
3. 本题我们应该初始化 dp[0] 为 1
4. 先遍历物品，再倒序遍历背包
5. 打印dp数组

为什么递推公式是这个：
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

dp[j] += dp[j - nums[i]]是之前本列的所有值，加上现在的dp[j - nums[i]，因为每次都加上了之前的dp[j]
比如之前只有物品1，容量j dp[j],现在多了物品2，那么所有情况就是 dp[j] = 之前只用物品1填满的 + 放入物品2后的，也就是dp[j] =dpj+dp[j - nums[i]]

组合问题记得初始化 dp[0] 因为跟计算价值不一样，如果dp[0]没有值，那么后面的数也都没有值

class Solution {
    // 背包问题求组合型
    // 设 x是正数部分，sum-x是负数部分 2x-sum = target ;  x = (target+sum)/2
    // 递推公式： dp[j]+=dp[j-nums[i]]
    // 怎么装能 装满x，有几种方法
    public int findTargetSumWays(int[] nums, int target) {
        if(nums == null || nums.length == 0 ){
            return 0;
        }
        int sum =0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        // 如果正数部分向下取整了，那就不可能，因为正数部分不可能是小数
        if((target+sum)%2 ==1){
            return 0;
        }
        int x = (target+sum)/2;
        // 如果总和的绝对值都比不过目标值，那就不可能
        if(Math.abs(sum) < Math.abs(target)){
            return 0;
        }
        // 装满容量为x的背包，有多少种方法
        int[] dp = new int[x+1];  
        dp[0] =1 ;
        for(int i=0;i<nums.length;i++){
            for(int j=x;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }   
        }
        return dp[x];

    }
}

01背包二维物品

有的时候物品维度有可能是二维的：

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

主要是要想到本题 用二维数组分别放 m和n的容量，那么循环就要循环三次，先物品，再倒叙循环两个背包：必须倒序，因为这个二维数组没有物品这个纬度，和之前的一维数组一样。

class Solution {
    // 还是01背包，物品是二维的，所以要用二维循环来遍历物品
    public int findMaxForm(String[] strs, int m, int n) {
      if(strs == null || strs.length == 0){
          return 0;
      }
      int[][] dp = new int[m+1][n+1];  // 最多放m个0，n个1，能最多放的子集数
      for(String s:strs){ // 遍历物品
            int oneCount = 0;
            int zeroCount = 0;
            for(char c:s.toCharArray()){
                if(c == '0'){
                    zeroCount++;
                } else {
                    oneCount++;
                }
            }
            for(int i=m;i>=zeroCount;i--){
                for(int j=n;j>=oneCount;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroCount][j-oneCount]+1);
                }
            }
      }
      return dp[m][n];
    }

}

完全背包

完全背包和01背包的区别就是一个物品可以装多次，和01背包的区别就是遍历背包的时候不是逆序而是正序：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

正序遍历意味着使用的是本个物品已经更新过的dp值了，所以有添加多次的效果。

完全背包组合问题

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1

这里是引用

5=2+1+1+1
5=1+1+1+1+1

递推公式和01背包组合问题一样，只是背包要正序遍历了：

class Solution {
    // 完全背包的组合问题
    public int change(int amount, int[] coins) {
        if(coins == null || coins.length == 0){
            return 0;
        }
        int[] dp = new int[amount+1];    // 有几种方式可以凑总金额为数组下标值的
        dp[0] = 1;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                     dp[j]+=dp[j-coins[i]];
              }
       }
       return dp[amount];
    }
}

完全背包排列问题

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

排列问题和组合问题的递推公式相同，只是遍历顺序相反，需要先遍历背包再遍历物品

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 完全背包排列问题
    if(nums ==null){
    return 0;
    }
    int[] dp = new int[target+1];
    dp[0] = 1;
    for(int j=1;j<=target;j++){
        for(int i=0;i<nums.length;i++){
            if(j>=nums[i])
            dp[j]+=dp[j-nums[i]];
        }
    }
    return dp[target];
    }
}

完全背包求最小值

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

求最小值提醒要注意的就是初始化，初始化的时候要把dp数组设置成int的最大值，但是dp[0]要为0，要不结果就全是最大值了

class Solution {
    public int coinChange(int[] coins, int amount) {
    if(coins ==null){   
    return 0;
    }
    int[] dp = new int[amount+1];  // 装满amount容量所需最少的硬币数
    for(int i=1;i<dp.length;i++){
        dp[i] = Integer.MAX_VALUE-1;
    }
    for(int i=0;i<coins.length;i++){
        for(int j=coins[i];j<=amount;j++){
               dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
        }
    }
    return dp[amount] == Integer.MAX_VALUE-1? -1:dp[amount];   // 没找到返回-1
    }
}

完全背包布尔型

139. 单词拆分

139. 单词拆分
     给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

这道题目也不完全是完全背包类型，因为遍历物品并不是遍历的字符数组，而是遍历字符串s的一部分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
         // 类似于完全背包排列问题 boolean型 背包是s，物品是数组
        boolean[] dp = new boolean[s.length()+1]; // 字符串长度为i时，判断可不可以由词典组成
        HashSet<String> set = new HashSet<>(wordDict);
        dp[0] = true; // 0这里视为空字符 不是第一个字符，因为要保留dp[0] 为true才有后面的值
        for(int j=1;j<=s.length();j++){    // 背包
            for(int i=0;i<j && !dp[j];i++){    // 物品
             // substring是左闭右开型的    
             // 注意dp[i]这个i延后了一位，代表的是 0到i-1位能不能被词典组成，s.substring(i,j)代表i到j-1位能不能被组成，如果都可以那么这个长度为j的字符（0到j-1位都满足），就满足了
                if(set.contains(s.substring(i,j)) && dp[i]){
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

子序列问题

在面试中 子序列问题倒是经常遇到，需要重视一下，还有股票问题，打家劫舍一起看图：

我发现子序列的一个规律：

求的是子序列（不连续）就是dp数组的含义就是从0到i，如果是连续的就是以i为结尾的连续子序列

在一个数组或字符串中求，dpi j可以表示数组的第i位，第j位，如果在两个里面求最好dp i j表示数组的第i-1位，j-1位，减少了初始化的麻烦

而且往往最终结果是在某一个dp值中的，不一定是最后一个。

难点就在于思考怎么设计dp数组，以及不同情况的递推公式

最长回文子串 hot100第5题

有个常出现的题，代码随想录里没有：

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

比较好的方法：中心扩散法
遍历s，每个字符向左右两边扩散，有奇数偶数两个情况 start = i - (max-1)/2; 这个比较骚

class Solution {
    // 中心拓展法
    public String longestPalindrome(String s) {
        int result = 0;
        int start = 0,end = 0;
        for(int i=0;i<s.length();i++){
            int one = centerExpand(s,i,i);     // 以i向左右扩散
            int middle = centerExpand(s,i,i+1);  // 以i和i+1向左右扩散
            int max = Math.max(one,middle);
            if(max > end - start){
                start = i - (max-1)/2;    // 这个用到了一些技巧，可以自己试一试
                end = i + max/2;
            }
        }
        return s.substring(start,end+1);
    }

    public int centerExpand(String s,int left,int right){
        // 从这个点 统计回文串长度
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){ 
            left--;
            right++;
        }
        return right-left-1;
    }

}

动态规划法：

class Solution {
    // 动态规划法
    public String longestPalindrome(String s) {
         int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        for(int i =0 ;i<len;i++){
            dp[i][i] = true;
        }

        char[] charArray = s.toCharArray();
        // 先遍历列，因为递推公式需要用到左下角的值
        for(int j=1;j<len;j++){
            for(int i = 0;i<j;i++){
                if(charArray[i] != charArray[j]){
                    dp[i][j] = false;
                } else {
                    // i j之间没有数或者只有一个数了 就是真
                    if(j-i<3){
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 有新结果记录位置
                if(dp[i][j] && j-i+1 > maxLen){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }

}

子序列（不连续）

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

遍历i的时候，要遍历0到i之前的每个，找到最大的连续子序列，然后加1就是dp[i]

为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。

dp是必须以i为结尾的，所以要记录最大值，因为最后一个字符结尾的不一定是最大的

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length ==0){
            return 0;
        }
       int[] dp = new int[nums.length];  // dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
       // 第i个数和第j个数比较，如果比j大，那么i的最长自增子序列就是j的加1，当然j的加1并不一定是i最长的，所以从0到i-1比较最大值
       
       int maxResult = 1;
       for(int i=1;i<nums.length;i++){
           for(int j=0;j<i;j++){
               if(nums[i] > nums[j])
               dp[i] = Math.max(dp[i],dp[j]+1);   // max中的dp[i]为的就是在第二层循环中找最大值
           }
            maxResult = Math.max(maxResult,dp[i]);
       }

       return maxResult;
    }   
}

子序列（连续）

674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。

注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置。

本题只需要比较i和i的前一个位置就行了，比较简单

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];  // dp[i] 以nums[i]结尾的最长连续递增序列
        int max = 1;
        for(int i=0;i<nums.length;i++){
           dp[i] = 1;
       }
        // 1 3 5 4 7
   // dp.  1 2 3 1 2
   //      1 2 3 0 
       for(int i=1;i<nums.length;i++){
           if(nums[i]>nums[i-1]){
               dp[i] =  dp[i-1]+1;  // 传递当前最大
           } 
           max=  Math.max(max,dp[i]);   // 传递历史最大
            
       }
       return max;
    }
}

最长公共子序列

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

有同学会问：为什么要定义长度为[0, i - 1]的字符串text1，定义为长度为[0, i]的字符串text1不香么？

这样定义是为了后面代码实现方便，如果非要定义为长度为[0, i]的字符串text1也可以,但是 需要初始化为0的情况，不太方便。

所以当求两个数组的公共最长子序列时，dp数组代表的最好是 i-1和j-1，因为是子序列，本题代表的是从0开始。。文章来源地址https://www.toymoban.com/news/detail-714483.html

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp =new int[text1.length()+1][text2.length()+1]; // 长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
        // dp[i][j] = Math.max(dp[i-1][j-1])
        int result =0;
        for(int i =1;i<=text1.length();i++){
            for(int j=1;j<=text2.length();j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    // 如果相同的话 abc abc 判断两个c的时候，是不是应该在 ab 和 ab 的基础上加1 啊
                    dp[i][j] = dp[i-1][j-1]+1;
                } else {
                    // 如果不相同的话，如abc 和 ace 判断 c和e的时候，c和e已经不相同了，那么就判断 abc和ac 或者ab和ace看谁最大，大的不就是 最长的公共子序列吗
                     dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
               
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

到了这里，关于算法笔记（Java）——动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！