美文网首页Algorithm
Algorithm进阶计划 -- 动态规划(下)

Algorithm进阶计划 -- 动态规划(下)

作者: 开心wonderful | 来源:发表于2021-10-09 17:40 被阅读0次

    经典动态规划

    • 背包问题
    • 最长子序列问题
    图片来源于网络

    1. 背包问题

    1.1 0-1 背包问题

    0-1 背包问题,描述如下:

    给你一个可装载重量为 W 的背包和 N 个物品,每个物品有重量和价值两个属性。
    其中第 i 个物品的重量为 wt[i],价值为 val[i],让你用这个背包装物品,最多能装的价值是多少?
    
    // 输入:
    N = 3, W = 4
    wt = [2, 1, 3]
    val = [4, 2, 3]
    // 输出:
    6 (解释:选择前两件物品装进背包,总重量 3 小于 W,可以获得最大价值 6)
    

    上面是一个典型的动态规划问题,物品不可以分割,要么装进包里,要么不装,不能说切成两块装一半。

    接下来按照动态规划标准套路进行演示:

    第一步:要明确两点,「状态」和「选择」。

    • 状态:就是 背包的容量可选择的物品
    • 选择:就是 装进背包不装进背包

    有了状态和选择,套入框架如下:

    for 状态1 in 状态1的所有取值:
        for 状态2 in 状态2的所有取值:
            for ...
                dp[状态1][状态2][...] = 择优(选择1,选择2...)
    

    第二步:要明确 dp 数组的定义。

    dp 数组是描述问题局面的一个数组,用它把状态表示出来,定义如下:

    dp[i][w] 的定义:对于前 i 个物品,当前背包的容量为 w,这种情况下可以装的最大价值是 dp[i][w]

    dp[3][5] = 6 表示只对前 3 个物品进行选择,当背包容量为 5 时,最多可以装下的价值为 6。

    根据定义,要求的最终答案就是 dp[N][W]。base case 就是 dp[0][..] = dp[..][0] = 0。(没物品或背包没空间时能装的最大价值是 0)。

    细化框架如下:

    int dp[N+1][W+1]
    dp[0][..] = 0
    dp[..][0] = 0
    
    for i in [1..N]:
        for w in [1..W]:
            dp[i][w] = max(
                把物品 i 装进背包,
                不把物品 i 装进背包
            )
    return dp[N][W]
    

    第三步:根据「选择」,思考状态转移的逻辑。

    这一步要结合对 dp 数组的定义和算法逻辑来分析:

    • 若没有把第 i 个物品装入背包,那么最大价值 dp[i][w] 等于 dp[i-1][w]
    • 若把第 i 个物品装入了背包,那么 dp[i][w] 等于 dp[i-1][w-wt[i-1]] + val[i-1]

    综上两种选择,进一步细化代码如下:

    for i in [1..N]:
        for w in [1..W]:
            dp[i][w] = max(
                dp[i-1][w],
                dp[i-1][w - wt[i-1]] + val[i-1]
            )
    return dp[N][W]
    

    最后:把伪码翻译成代码,处理一些边界情况。

    这边主要处理 w - wt[i-1] 可能小于 0 导致数组索引越界的问题,如下:

        /**
         * 0-1 背包问题
         *
         * @param w   背包可装载的重量
         * @param n   物品的数量
         * @param wt  物品对应的重量
         * @param val 物品对应的价值
         */
        public int knapsack(int w, int n, int[] wt, int[] val) {
    
            // dp[i][w]定义:对于前i个物品,当前背包的容量为w,这种情况下可以装的最大价值是dp[i][w]
            int[][] dp = new int[n + 1][w + 1];
            for (int i = 0; i < n; i++) {
                dp[i][0] = 0;
            }
            for (int j = 0; j < w; j++) {
                dp[0][j] = 0;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= w; j++) {
                    if (j - wt[i - 1] < 0) {
                        // 当前背包容量装不下,只能选择不装入背包
                        dp[i][j] = dp[i - 1][w];
                    } else {
                        // 装入或者不装入背包,择优
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][w - wt[i - 1] + val[i - 1]]);
                    }
                }
            }
    
            return dp[n][w];
        }
    

    1.2 分割等和子集

    力扣 416 题如下:

    分割等和子集

    这道题其实就是 0-1 背包问题的变体,转化为背包问题描述如下:

    给一个可装载重量为 sum/2 的背包和 N 个物品,每个物品的重量为 nums[i]。是否存在一种装法,能够恰好将背包装满?

    第一步:要明确「状态」和「选择」。

    • 状态: 背包的容量 和 可选择的物品
    • 选择: 装进背包 或 不装进背包

    第二步:要明确 dp 数组的定义。

    dp[i][j] = x 表示,对于前 i 个物品,当前背包的容量为 j 时,若 xtrue,则说明恰好能将背包装满,否则不能。

    根据这个定义,要求的最终答案是 dp[N][sum/2],base case 就是 dp[..][0] = truedp[0][..] = false,即背包没空间时相当于装满了,而当没物品可选择时没办法装满背包。

    第三步:根据「选择」,思考状态转移的逻辑。

    根据「选择」对 dp[i][j] 得到以下状态转移:

    • 不把 nums[i]算入子集(不把这第 i 个物品装入背包),是否能够恰好装满背包,取决于上一个状态 dp[i-1][j]
    • nums[i] 算入子集(把这第 i 个物品装入背包),是否能够恰好装满背包,取决于状态 dp[i - 1][j-nums[i-1]]

    最后:处理一些边界情况,代码实现如下:

        /**
         * 分割等和子集 -- 0-1 背包问题变种
         * <p>
         * 先对集合求和,得出 sum,给一个可装载重量为 sum/2 的背包和 N 个物品,每个物品的重量为 nums[i]。
         * 是否存在一种装法,能够恰好将背包装满?
         */
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
    
            // 和为奇数时,不可能划分成两个和相等的集合
            if (sum % 2 != 0) return false;
    
            int n = nums.length;
            sum = sum / 2;
            // dp[i][j] = x 定义:对于前 i 个物品,当前背包的容量为 j 时,若 x 为 true,则说明恰好能将背包装满,否则不能。
            boolean[][] dp = new boolean[n + 1][sum + 1];
    
            // base case
            for (int i = 0; i <= n; i++) {
                dp[i][0] = true;
            }
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= sum; j++) {
                    if (j - nums[i - 1] < 0) {
                        // 背包容量不足,不能装入第 i 个物品
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        // 装入或不装入背包
                        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]];
                    }
                }
            }
            return dp[n][sum];
        }
    

    值得注意的是,上面 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过来的,因此可进行状态压缩如下:

        /**
         * 分割等和子集 -- 0-1 背包问题变种
         * <p>
         * 进行状态压缩,将二维dp数组压缩为一维,节约空间复杂度
         */
        public boolean canPartition(int[] nums) {
            int sum = 0, n = nums.length;
            for (int num : nums) sum += num;
            if (sum % 2 != 0) return false;
            sum = sum / 2;
            boolean[] dp = new boolean[sum + 1];
            // base case
            dp[0] = true;
    
            for (int i = 0; i < n; i++) {
                for (int j = sum; j >= 0; j--) {
                    if (j - nums[i] >= 0) {
                        dp[j] = dp[j] || dp[j - nums[i]];
                    }
                }
            }
    
            return dp[sum];
        }
    

    上面值得注意的是,j 从后往前反向遍历,因为每个物品(或者说数字)只能用一次,以免之前的结果影响其他的结果。

    时间复杂度 O(n*sum),空间复杂度 O(sum)。

    2. 最长子序列问题

    2.1 最长递增子序列

    最长递增子序列(Longes Increasing Subsequence,简写为 LIS)。

    力扣 300 题如下:

    最长递增子序列

    动态规划的核心设计思想是 数学归纳法

    数学归纳法的思路如下:要证明一个数学结论,先假设这个结论在 k<n 时成立,然后根据这个假设,想办法推导证明 k=n 时此结论也成立。若能证明出来,就说明此结论对于 k 是任何数都成立。

    类似的,设计动态规划算法,需要一个 dp 数组,先假设 dp[0...i-1] 都已经被算出来了,然后想办法通过这些结果算出 dp[i]

    对于最长递增子序列明确 dp 数组的定义:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度

    根据这个定义,可以推出 base case:dp[i] 初始值为 1 (以 nums[i] 结尾的最长递增子序列起码要包含它自己)。最终结果是 dp 数组中的最大值。

    代码实现如下:

        /**
         * 最长递增子序列
         * <p>
         * dp 数组的定义:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
         * <p>
         * 时间复杂度:O(N^2)
         */
        public int lengthOfLIS(int[] nums) {
            int[] dp = new int[nums.length];
    
            // base case: dp 数组初始化为 1
            Arrays.fill(dp, 1);
    
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        // 因为是递增子序列,只要找到前面那些结尾比 nums[i] 小的子序列,
                        // 然后把 nums[i] 接到最后,就可以形成一个新的递增子序列,而且这个新的子序列长度加一。
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
    
            // 最终结果(子序列的最大长度)是 dp 数组中的最大值
            int res = 0;
            for (int len : dp) {
                res = Math.max(res, len);
            }
            return res;
        }
    

    小结:

    1. 明确 dp 数组所存数据的含义。

    2. 根据 dp 数组的定义,运用数学归纳法的思想,假设 dp[0...i-1] 都已知,想办法求出 dp[i]

    当然上面这题也可以用二分查找法来解,时间复杂度更低为 O(NlogN),如下:

         /**
         * 最长递增子序列 -- 二分查找
         * <p>
         * 时间复杂度: O(NlogN)
         */
        public int lengthOfLis(int[] nums) {
            int[] top = new int[nums.length];
            // 牌堆数初始化为 0
            int piles = 0;
            for (int i = 0; i < nums.length; i++) {
                // 要处理的扑克牌
                int poker = nums[i];
    
                // 搜索左侧边界的二分查找
                int left = 0, right = piles;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (top[mid] > poker) {
                        right = mid;
                    } else if (top[mid] < poker) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                // 没找到合适的牌堆,新建一堆
                if (left == piles) piles++;
                // 把这张牌放到牌堆顶
                top[left] = poker;
            }
            // 牌堆数就是 LIS 长度
            return piles;
        }
    

    2.2 俄罗斯套娃信封问题

    力扣 354 题如下:

    俄罗斯套娃信封问题

    这题其实是上面最长递增子序列的一个变种,每次合法的嵌套是大的套小的,相当于找一个最长递增的子序列,其长度就是最多能嵌套的信封个数。

    解题思路:先对宽度 w 进行升序排序,如果遇到 w 相同的情况,则按照高度 h 降序排序。之后把所有的 h 作为一个数组,在这个数组上计算 LIS 的长度就是答案

    代码实现如下:

        /**
         * 俄罗斯套娃信封问题
         *
         * @param envelopes envelopes[i] = [wi, hi] ,表示第 i 个信封的宽度和高度
         */
        public int maxEnvelopes(int[][] envelopes) {
            int n = envelopes.length;
            // 按宽度升序排列,若宽度一样则按高度降序排列
            Arrays.sort(envelopes, new Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
                }
            });
            // 对高度数组寻找 LIS
            int[] height = new int[n];
            for (int i = 0; i < n; i++) {
                height[i] = envelopes[i][1];
            }
            return lengthOfLis(height);
        }
    
        /**
         * 最长递增子序列 
         */
        private int lengthOfLis(int[] nums) {
            int[] top = new int[nums.length];
            int piles = 0;
            for (int i = 0; i < nums.length; i++) {
                int poker = nums[i];
                int left = 0, right = piles;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (top[mid] > poker) {
                        right = mid;
                    } else if (top[mid] < poker) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                if (left == piles) piles++;
                top[left] = poker;
            }
            return piles;
        }
    

    上面时间复杂度为 O(NlogN),空间复杂度为 O(N)。

    2.3 最长子序和

    力扣 53 题如下:

    最长子序和

    滑动窗口算法是专门处理子串/子数组问题的,但这道题数组中的数字可以是负数(会有无法判断何时收缩窗口的情况),因而不能用滑动窗口算法。

    这道题和上面的最长递增子序列很相似,定义 dp 数组如下:nums[i] 为结尾的「最大子数组和」为 dp[i]

    根据这个定义,最后遍历整个 dp 数组寻找最大值即可:

    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
    

    现假设已算出 dp[i-1],那么 dp[i] 有两种「选择」,要么与前面的相邻子数组连接,形成一个和更大的子数组;要么不与前面的子数组连接,自成一派,自己作为一个子数组。如下:

    // 要么自成一派,要么和前面的子数组合并
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    

    代码实现如下:

        /**
         * 最大子序和
         * <p>
         * dp 数组的定义:以nums[i]为结尾的「最大子数组和」为dp[i]
         */
        public int maxSubArray(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            int[] dp = new int[n];
    
            // base case: 第一个元素前面没有子数组
            dp[0] = nums[0];
            // 状态转移方程
            for (int i = 1; i < n; i++) {
                dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            }
    
            // 得到 nums 的最大子数组
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    

    上面时间、空间复杂度都是 O(N),注意到 dp[i] 仅仅和 dp[i-1] 的状态有关,还可以进一步状态压缩,把空间复杂度降低:

        /**
         * 最大子序和
         */
        public int maxSubArray(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
    
            // base case:
            int dp_0 = nums[0];
            int dp_1 = 0, res = dp_0;
            // 状态转移方程
            for (int i = 1; i < n; i++) {
                // dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
                dp_1 = Math.max(nums[i], nums[i] + dp_0);
                dp_0 = dp_1;
                // 顺便计算最大的结果
                res = Math.max(res, dp_1);
            }
    
            return res;
        }
    

    小结:定义 dp 数组时要注意 dp[i-1]dp[i] 要建立起联系,再利用数学归纳法写出状态转移方程。

    2.4 最长公共子序列

    计算最长公共子序列(Longest Common Subsequence,简称 LCS)是一道经典的动态规划题目。

    力扣 1143 题如下:

    最长公共子序列

    对于两个字符串求子序列的问题,都是用两个指针 ij 分别在两个字符串上移动,大概率是动态规划思路。

    首先,定义 dp 函数如下:dp(s1, i, s2, j) 计算 s1[i..]s2[j..] 的最长公共子序列长度

    根据这个定义,最终答案就是 dp(s1, 0, s2, 0),base case 就是 i == len(s1)j == len(s2) 时:

    int longestCommonSubsequence(String s1, String s2) {
        return dp(s1, 0, s2, 0);
    }
    
    // 定义:计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
    int dp(String s1, int i, String s2, int j) {
        // base case
        if (i == s1.length() || j == s2.length()) {
            return 0;
        }
        // ...
    

    接着,实现 dp 函数:

        /**
         * 定义:dp(s1, i, s2, j)计算s1[i..]和s2[j..]的最长公共子序列长度。
         */
        private int dp(String s1, int i, String s2, int j) {
            // base case
            if (i == s1.length() || j == s2.length()) {
                return 0;
            }
    
            if (s1.charAt(i) == s2.charAt(j)) {
                // s1[i] 和 s2[j] 必然在 lcs 中,
                // 加上 s1[i+1..] 和 s2[j+1..] 中的 lcs 长度,就是答案
                return 1 + dp(s1, i + 1, s2, j + 1);
            } else {
                // s1[i] 和 s2[j] 中至少有一个字符不在 lcs 中,
                // 穷举三种情况的结果,取其中的最大结果
                return max(
                        // 情况一、s1[i] 不在 lcs 中
                        dp(s1, i + 1, s2, j),
                        // 情况二、s2[j] 不在 lcs 中
                        dp(s1, i, s2, j + 1),
                        // 情况三、都不在 lcs 中(这种情况可忽略)
                        dp(s1, i + 1, s2, j + 1)
                );
            }
        }
    
        private int max(int a, int b, int c) {
            return Math.max(a, Math.max(b, c));
        }
    

    以上便是暴力穷举法。

    最后,用备忘录的方法消除重叠子问题,如下:

        /**
         * 最长公共子序列
         */
        public int longestCommonSubsequence(String s1, String s2) {
            int m = s1.length();
            int n = s2.length();
    
            // 备忘录
            int[][] memo = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    memo[i][j] = -1;
                }
            }
    
            return dp(memo, s1, 0, s2, 0);
        }
    
        /**
         * 定义:dp(s1, i, s2, j)计算s1[i..]和s2[j..]的最长公共子序列长度。
         */
        private int dp(int[][] memo, String s1, int i, String s2, int j) {
            // base case
            if (i == s1.length() || j == s2.length()) {
                return 0;
            }
    
            // 查找备忘录
            if (memo[i][j] != -1) return memo[i][j];
    
            if (s1.charAt(i) == s2.charAt(j)) {
                // s1[i] 和 s2[j] 必然在 lcs 中,
                memo[i][j] = 1 + dp(memo, s1, i + 1, s2, j + 1);
            } else {
                // s1[i] 和 s2[j] 中至少有一个字符不在 lcs 中,
                memo[i][j] = Math.max(
                        dp(memo, s1, i + 1, s2, j),
                        dp(memo, s1, i, s2, j + 1)
                );
            }
    
            return memo[i][j];
        }
    

    当然,也可以用 DP table 来解,如下:

        /**
         * 最长公共子序列 -- DP table
         */
        public int longestCommonSubsequence2(String s1, String s2) {
            int m = s1.length();
            int n = s2.length();
    
            // 定义:s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
            // 目标:s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度,即 dp[m][n]
            // base case: dp[0][..] = dp[..][0] = 0
            int[][] dp = new int[m + 1][n + 1];
            for(int i = 0; i < m; i++){
                dp[i][0] = 0;
            }
            for(int j = 0; j < n; j++){
                dp[0][j] = 0;
            }
    
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                        // s1[i-1] 和 s2[j-1] 必然在 lcs 中
                        dp[i][j] = 1 + dp[i - 1][j - 1];
                    } else {
                        // s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                    }
                }
            }
    
            return dp[m][n];
        }
    

    2.5 两个字符串的删除操作

    力扣 583 题如下:

    两个字符串的删除操作

    显然,上面的删除的结果就是它俩的最长公共子序列,因此容易推算出所需删除的次数:

        /**
         * 两个字符串的删除操作
         */
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
    
            // 最长公共子序列
            int lcs = longestCommonSubsequence(word1, word2);
    
            return m - lcs + n - lcs;
        }
    

    2.6 两个字符串的最小ASCII删除和

    力扣 712 题如下:

    两个字符串的最小ASCII删除和

    这道题还是依照之前的思路,修改 base case 和状态转移部分即可直接写出解法代码:

        /**
         * 两个字符串的最小ASCII删除和
         */
        public int minimumDeleteSum(String s1, String s2) {
            int m = s1.length();
            int n = s2.length();
    
            // 备忘录
            int[][] memo = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    memo[i][j] = -1;
                }
            }
    
            return dp2(memo, s1, 0, s2, 0);
        }
    
        /**
         * 定义:将 s1[i..] 和 s2[j..] 删除成相同字符串,最小的 ASCII 码之和为 dp(s1, i, s2, j)。
         */
        private int dp2(int[][] memo, String s1, int i, String s2, int j) {
            int res = 0;
            // base case
            if (i == s1.length()) {
                // 如果 s1 到头了,那么 s2 剩下的都得删除
                for (; j < s2.length(); j++) {
                    res += s2.charAt(j);
                }
                return res;
            }
            if (j == s2.length()) {
                // 如果 s2 到头了,那么 s1 剩下的都得删除
                for (; i < s1.length(); i++) {
                    res += s1.charAt(i);
                }
                return res;
            }
    
            // 查找备忘录
            if (memo[i][j] != -1) return memo[i][j];
    
            // 添加备忘录
            if (s1.charAt(i) == s2.charAt(j)) {
                // s1[i] 和 s2[j] 都是在 lcs 中的,不用删除
                memo[i][j] = dp2(memo, s1, i + 1, s2, j + 1);
            } else {
                // s1[i] 和 s2[j] 至少有一个不在 lcs 中,删一个
                memo[i][j] = Math.min(
                        s1.charAt(i) + dp2(memo, s1, i + 1, s2, j),
                        s2.charAt(j) + dp2(memo, s1, i, s2, j + 1)
                );
            }
    
            return memo[i][j];
        }
    

    2.7 最长回文子序列

    力扣 516 题如下:

    最长回文子序列

    首先,定义一个 dp 函数:在子串 s[i..j] 中,最长回文子序列的长度为 dp[i][j]

    根据定义, 若只有一个字符,则最长回文子序列长度是 1,即 base case 就是 dp[i][j] = 1,(i == j)。而对于那些 i > j 的位置,不存在什么子序列,应初始化为 0。

    接着,dp[i][j] 的值取决于 s[i]s[j] 的字符,实现 dp 函数逻辑如下:

    if (s[i] == s[j])
        // 若相等,它俩一定在最长回文子序列中
        dp[i][j] = dp[i + 1][j - 1] + 2;
    else
        // 若不等,s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长?
        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
    

    最后,代码实现如下:

        /**
         * 最长回文子序列
         */
        public int longestPalindromeSubseq(String s) {
            int n = s.length();
    
            // dp 数组定义: 在子串 s[i..j] 中,最长回文子序列的长度为 dp[i][j]
            int[][] dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = 0;
                }
            }
    
            // base case
            for (int i = 0; i < n; i++) {
                dp[i][i] = 1;
            }
            // 反着遍历保证正确的状态转移
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i + 1; j < n; j++) {
                    // 状态转移方程
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
    
            // 整个 s 的最长回文子串长度
            return dp[0][n - 1];
        }
    

    小结:

    对于子序列问题,主要是 dp 数组的定义思路,不同的问题可能需要不同的 dp 数组定义来解决。

    • 思路一:一个一维的 dp 数组
    int n = array.length;
    int[] dp = new int[n];
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = 最值(dp[i], dp[j] + ...)
        }
    }
    

    比如最长递增子序列就是这种思路,dp 数组的含义如下:
    在子数组 array[0..i] 中,以 array[i] 结尾的目标子序列(最长递增子序列)的长度是 dp[i]

    • 思路一:一个二维的 dp 数组
    int n = arr.length;
    int[][] dp = new dp[n][n];
    
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (arr[i] == arr[j]) 
                dp[i][j] = dp[i][j] + ...
            else
                dp[i][j] = 最值(...)
        }
    }
    

    这种思路运用相对多一些,尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。

    涉及两个字符串/数组时(比如最长公共子序列),dp 数组的含义如下:
    在子数组 arr1[0..i] 和子数组 arr2[0..j] 中,我们要求的子序列(最长公共子序列)长度为 dp[i][j]

    只涉及一个字符串/数组时(比如最长回文子序列),dp 数组的含义如下:
    在子数组 array[i..j] 中,我们要求的子序列(最长回文子序列)的长度为 dp[i][j]


    参考链接:

    经典动态规划:0-1 背包问题

    动态规划设计:最长递增子序列

    最长递增子序列之信封嵌套问题

    动态规划设计:最大子数组

    经典动态规划:最长公共子序列

    相关文章

      网友评论

        本文标题:Algorithm进阶计划 -- 动态规划(下)

        本文链接:https://www.haomeiwen.com/subject/jdcjnltx.html