动态规划问题解题思路

1. 动态规划的核心思想

动态规划的本质是：通过聪明地穷举来避免重复计算。它将复杂问题分解为相互重叠的子问题，通过保存子问题的解（记忆化）来避免重复计算，从而高效地求解原问题。

关键特征（适用DP的问题特点）：

1. 最优子结构：问题的最优解包含其子问题的最优解

2. 重叠子问题：在求解过程中，相同的子问题会被多次重复计算

2. 动态规划的两种实现方式

看变量的个数，确认用哪一种动态规划

一个变量，一维动态规划，例如：打家劫舍，爬楼梯，一维背包

两个变量，二维动态规划，例如：回文串（难想，实际上是两个端点），二维背包（个数、容量）

方式一：自顶向下 - 记忆化搜索（递归 + 备忘录）

// 伪代码
int dp(状态参数) {
    if (基本情况) return 基础解;
    if (状态已计算过) return 缓存的结果;
    
    int result = 根据状态计算的结果;
    缓存当前状态的结果;
    return result;
}

方式二：自底向上 - 迭代法（DP Table）

// 伪代码
初始化dp数组;
for (状态1 的所有取值) {
    for (状态2 的所有取值) {
        for (...) {
            dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...);
        }
    }
}
return dp[最终状态];

其实方式二更符合常规思维，即先完成初始状态的枚举，然后递推到更靠后的场景

3. 通用动态规划思维框架

解决任何DP问题，都可以遵循以下四步曲：

第一步：定义DP数组的含义

明确dp[i]或dp[i][j]代表什么含义。

例子：

• 斐波那契数列：dp[i]表示第i个斐波那契数

• 背包问题：dp[i][w]表示前i个物品，背包容量为w时的最大价值

• 最长公共子序列：dp[i][j]表示text1[0..i]和text2[0..j]的最长公共子序列长度

第二步：确定状态转移方程

这是DP的核心，找出dp[i]与之前状态的关系。

例子：

• 斐波那契：dp[i] = dp[i-1] + dp[i-2]

• 爬楼梯：dp[i] = dp[i-1] + dp[i-2]

• 零钱兑换：dp[i] = min(dp[i], dp[i - coin] + 1)

第三步：初始化基础情况

确定最简单子问题的解。

例子：

• 斐波那契：dp[0] = 0, dp[1] = 1

• 爬楼梯：dp[0] = 1, dp[1] = 1（或dp[1] = 1, dp[2] = 2）

• 最长递增子序列：每个dp[i]至少为1

第四步：确定遍历顺序

确保在计算dp[i]时，所需要的子问题都已经被计算过。

例题

【leetcode5. 最长回文串 - 二维】

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

示例 1：

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

动态规划递推思维：

• S[i, j]是回文串 -> S[i+1, j-1]是回文串 && S[i-1] == S[j-1]

• S[i, j] i=j，return true；i + 1 = j ,如果S[i] = S[j] return true

• 边界条件：i > j 恒返回false

• 斜向递推，因为确认S[i, j]需要先确认S[i - 1, j - 1]，画二维表就可以看出，其实是向左上角取值的

class Solution {
    public String longestPalindrome(String s) {
        // S[i, j]是回文串 -> S[i+1, j-1]是回文串 && S[i-1] == S[j-1]
        // S[i, j] i=j，return true；i + 1 = j ,如果S[i] = S[j] return true
        // i > j 恒返回false
        char[] charArray = s.toCharArray();
        boolean [][] dp = new boolean[s.length()][s.length()];
        String result = "";
        // 初始化i = j场景
        for (int index = 0; index < s.length(); index ++) {
            dp[index][index] = true;
        }
        result = s.substring(0, 1);
        if (s.length() == 1) {
            return s;
        }
        // 初始化i + 1 = j的场景
        for (int index = 0; index + 1 < s.length(); index ++) {
            if (charArray[index] == charArray[index + 1]) {
                dp[index][index + 1] = true;
                result = s.substring(index, index + 2);
            }
        }
        if (s.length() == 2) {
            return result;
        }
        int length = 2;

        while (true) {
            int i = 0;
            if (i + length > s.length() - 1) {
                break;
            }
            while (true) {
                if (i + length > s.length() - 1) {
                    break;
                }
                dp[i][i + length] = dp[i + 1][i + length - 1] && charArray[i] == charArray[i + length];
                if (dp[i][i + length]) {
                    if (i + length - i + 1 > result.length()) {
                        result = s.substring(i, i + length + 1);
                    }
                }
                i += 1;
            }
            length += 1;
        }
        return result;

    }
}

怎么实现的斜向？即每次行+1，列+1，这样不好循环，不如改成行 + length

先写内存循环，每次i + 1，即行向下移动，直到 i + length超长

然后外层循环，每次length + 1，同时行数要归0，即重新从最上面开始递推，还是直到i + length超长

最后业务取值，即发现dp[i][j]为true，即是回文串，判断i、j间距，替换result结果