【算法】动态规划

一、算法概念

• 动态规划算法是一种解决多阶段决策问题的方法。它将一个问题分解为多个子问题，并逐个求解子问题的最优解，最后得到原问题的最优解。

二、基本思想

• 动态规划算法的核心思想是通过存储中间结果来避免重复计算。在解决问题的过程中，会利用已经求解过的子问题的最优解来求解当前问题的最优解。
• 动态规划算法可以解决很多实际问题，例如背包问题、最长公共子序列问题、最短路径问题等。它具有时间复杂度低、解决问题的范围广等优点，但在问题的状态转移方程的建立和初始状态的确定上需要一定的技巧和经验。

三、算法步骤

1. 定义问题的状态：将原问题拆分为若干个子问题，并定义每个子问题的状态。
2. 定义问题的状态转移方程：通过分析子问题之间的关系，建立起子问题之间的转移关系，即求解当前问题的最优解的公式。
3. 定义初始状态：确定最简单的子问题的最优解，作为初始状态。
4. 自底向上求解：从初始状态开始，按照状态转移方程逐步求解子问题的最优解，最终得到原问题的最优解。

四、简单实现示例【最长回文子串】

题干：

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

示例：

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

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解法：

class Solution {
    public String longestPalindrome(String s) {
         if(s.length()==1){
            System.out.println(s);
        }
        int start = 0;
        int maxLen = 1;
        char[] chars = s.toCharArray();
        if(chars.length == 1){
            System.out.println(chars);
        }
        boolean[][] dp = new boolean[chars.length][chars.length];
        for(int i=0; i<chars.length; i++){
            dp[i][i] = true;
        }
        for(int l=2; l<=chars.length; l++){
            for(int i=0; i<chars.length-1; i++){
                // 长度l = r-i + 1
                int r = l+i-1;
                // 条件判断一：判断大于右边界跳出本次
                if(r> chars.length-1){
                    break;
                }
                // 条件判断二：2个且相等
                if(chars[i] != chars[r]){
                    dp[i][r] = false;
                }else {
                    if(l<=3){
                        dp[i][r] = true;
                       
                    }else {
                        // 这里可以等于TRUE可以等于FALSE，所以更新初始索引及最大长度应该有个判断
                        dp[i][r] = dp[i+1][r-1];
                        
                    }
                }
                if(dp[i][r] == true){
                        start = i;
                        maxLen = l;
                }
               
            }
        }
        return s.substring(start, start+maxLen);
    }
}

具体步骤拆解：

1. 定义问题状态：
   • 定义dp[i][j]表示s的子串从索引 i 到索引 j 是否为回文子串，如果是则为true，否则为false。
2. 定义状态转移方程：
   • 当 i = j 时，dp[i][j] = true，单个字符肯定是回文子串。
   • 当 i ≠ j 时，如果 s[i] = s[j] 且 dp[i+1][j-1] = true 则dp[i][j]为回文子串。
3. 定义初始状态：
   • 对于长度为 1 的子串，即 i = j 的情况，dp[i][j] = true 。
4. 自底向上求解：
   从长度较短的子串向长度较长的子串逐步推导，可以使用变量记录子串的起始索引及长度，通过更新变量得到最长回文子串。
   • 遍历字符串 s，外层循环控制子串长度，内层循环控制子串的起始索引。假设当前的子串长度为 maxLen ，起始索引为 i，则结束索引为 r = i + maxLen - 1。
   • 根据状态转移方程判断子串是否为回文子串，如果是则更新最长回文子串的起始索引和长度。
5. 返回最长回文子串

五、10种常见应用场景及对应的步骤拆解

1. 最长递增子序列（Longest Increasing Subsequence）：
   • 定义状态：dp[i]表示以第i个元素结尾的最长递增子序列的长度。
   • 状态转移方程：dp[i] = max(dp[j] + 1)，其中j < i且nums[j] < nums[i]。
   • 初始条件：dp[i]的初始值为1。
   • 最终结果：遍历dp数组，找到最大的dp[i]，即为最长递增子序列的长度。

2. 最长公共子序列（Longest Common Subsequence）：
   • 定义状态：dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列的长度。
   • 状态转移方程：
     • 如果s1[i-1]等于s2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1。
     • 如果s1[i-1]不等于s2[j-1]，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
   • 初始条件：dp[0][j]和dp[i][0]的初始值都为0。
   • 最终结果：dp[m][n]，其中m和n分别为s1和s2的长度。

3. 0-1背包问题（0-1 Knapsack Problem）：
   • 定义状态：dp[i][j]表示前i个物品放入容量为j的背包可以获得的最大价值。
   • 状态转移方程：
     • 如果第i个物品可以放入背包（weights[i-1] <= j），则dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])。
     • 如果第i个物品不能放入背包（weights[i-1] > j），则dp[i][j] = dp[i-1][j]。
   • 初始条件：dp[0][j]和dp[i][0]的初始值都为0。
   • 最终结果：dp[n][W]，其中n为物品数量，W为背包的容量。

4. 最长回文子串（Longest Palindromic Substring）：
   • 定义状态：dp[i][j]表示字符串s从第i个字符到第j个字符是否为回文子串。
   • 状态转移方程：
     • 如果s[i]等于s[j]，且dp[i+1][j-1]为回文子串，则dp[i][j]为回文子串。
     • 如果s[i]不等于s[j]，则dp[i][j]不是回文子串。
   • 初始条件：dp[i][i]为true，dp[i][i+1]等于s[i]是否等于s[i+1]。
   • 最终结果：遍历dp数组，找到最长的回文子串。

5. 最小路径和（Minimum Path Sum）：
   • 定义状态：dp[i][j]表示到达网格位置(i, j)的最小路径和。
   • 状态转移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。
   • 初始条件：dp[0][j] = dp[0][j-1] + grid[0][j]，dp[i][0] = dp[i-1][0] + grid[i][0]。
   • 最终结果：dp[m-1][n-1]，其中m和n分别为网格的行数和列数。

6. 最大子数组和（Maximum Subarray）：
   • 定义状态：dp[i]表示以第i个元素结尾的最大子数组和。
   • 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])。
   • 初始条件：dp[0]等于nums[0]。
   • 最终结果：遍历dp数组，找到最大的dp[i]，即为最大子数组和。

7. 完全背包问题（Unbounded Knapsack Problem）：
   • 定义状态：dp[i]表示容量为i的背包可以获得的最大价值。
   • 状态转移方程：dp[i] = max(dp[i], dp[i-weights[j]] + values[j])，其中j为可选物品的索引。
   • 初始条件：dp[0]等于0。
   • 最终结果：dp[W]，其中W为背包的容量。

8. 编辑距离（Edit Distance）：
   • 定义状态：dp[i][j]表示将字符串word1的前i个字符转换为字符串word2的前j个字符所需的最小操作次数。
   • 状态转移方程：
     • 如果word1[i-1]等于word2[j-1]，则dp[i][j] = dp[i-1][j-1]。
     • 如果word1[i-1]不等于word2[j-1]，则dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。
   • 初始条件：dp[i][0]等于i，dp[0][j]等于j。
   • 最终结果：dp[m][n]，其中m和n分别为word1和word2的长度。

9. 最长有效括号（Longest Valid Parentheses）：
   • 定义状态：dp[i]表示以第i个字符结尾的最长有效括号的长度。
   • 状态转移方程：
     • 如果s[i]等于’)‘且s[i-1]等于’('，则dp[i] = dp[i-2] + 2。
     • 如果s[i]等于’)‘且s[i-1]等于’)‘，且s[i-dp[i-1]-1]等于’('，则dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2。
   • 初始条件：dp[0]等于0。
   • 最终结果：遍历dp数组，找到最大的dp[i]，即为最长有效括号的长度。

10. 最大正方形（Maximal Square）：
    • 定义状态：dp[i][j]表示以矩阵中第i行第j列的元素为右下角的最大正方形的边长。
    • 状态转移方程：
      • 如果matrix[i][j]等于’1’，则dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
      • 如果matrix[i][j]等于’0’，则dp[i][j]等于0。
    • 初始条件：dp[0][j]和dp[i][0]的初始值等于matrix[0][j]和matrix[i][0]的值。
    • 最终结果：遍历dp数组，找到最大的dp[i][j]，即为最大正方形的边长。

六、动态规划算法优缺点

优点：

1. 减少重复计算：动态规划算法通过将问题分解为子问题，并将子问题的解保存起来，避免了重复计算相同子问题，提高了算法的效率。
2. 提高算法效率：动态规划算法通常能够将问题的时间复杂度从指数级降低到多项式级别，大大提高了算法的效率。
3. 空间复杂度较低：动态规划算法通常只需要存储一些中间结果，而不需要保存所有可能的解，因此空间复杂度相对较低。

缺点：

1. 需要额外的空间来存储中间结果：动态规划算法需要使用数组、矩阵等数据结构来存储中间结果，会占用一定的额外空间。
2. 子问题的求解顺序不确定：在动态规划算法中，子问题的求解顺序通常不是固定的，需要根据问题的特点来确定子问题的求解顺序，这会增加算法的复杂性。
3. 不一定适用于所有问题：动态规划算法适用于具有重叠子问题和最优子结构性质的问题，但不是所有问题都具备这两个性质，因此动态规划算法并不适用于所有问题。

虽然动态规划算法存在一些缺点，但在很多实际问题中，动态规划算法仍然是一种非常有效的解决方法。通过合理的设计状态和状态转移方程，可以充分利用动态规划算法的优点，解决复杂的问题。