动态规划DP

斐波那契数列模型

斐波那契数列是动态规划的入门模型，其核心思想是当前状态由前几个状态线性组合而成。

• 状态定义：通常使用一维 dp 数组，dp[i] 表示第 i 个位置的数值。
• 状态转移方程：dp[i] = dp[i-1] + dp[i-2] + ...
• 初始化：根据递推公式，需要预先定义好前几个无法被推导出的状态值。

经典例题：第 N 个泰波那契数 (LeetCode 1137)

泰波那契序列 Tn 定义为：T0=0,T1=1,T2=1，且在 n≥0 的条件下 Tn+3=Tn+Tn+1+Tn+2。

C++ 优化代码 (滚动数组/状态压缩)

对于斐波那契类型的题目，由于 dp[i] 的计算只依赖于前几个固定状态，可以使用滚动数组（状态压缩）将空间复杂度从 O(N) 优化到 O(1)。

C++

#include <iostream>

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;

        // 使用状态压缩，仅保留最近的三个状态
        int a = 0, b = 1, c = 1;
        int d; // 用于计算新状态

        for (int i = 3; i <= n; ++i) {
            d = a + b + c;
            // 状态向前滚动
            a = b;
            b = c;
            c = d;
        }
        return c; // 最终结果存储在 c 中
    }
};

// int main() {
//     Solution sol;
//     std::cout << sol.tribonacci(25) << std::endl; // 输出: 1389537
//     return 0;
// }

路径问题

路径问题通常涉及在二维网格中，从起点到终点寻找特定路径（如总数、最小代价等）。

• 状态定义：dp[i][j] 通常表示到达网格位置 (i, j) 时的路径属性（如路径总数）。
• 状态转移方程：dp[i][j] 的值通常由其上方 dp[i-1][j] 和左方 dp[i][j-1] 的状态转移而来。
• 初始化：通常需要初始化网格的边界条件，例如第一行和第一列的路径值。

经典例题：不同路径 (LeetCode 62)

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或向右移动一步。问总共有多少条不同的路径可以到达网格的右下角。

C++ 优化代码 (空间优化)

观察到 dp[i][j] 的计算只依赖于当前行和上一行的数据，因此可以将二维 dp 数组压缩为一维。

C++

#include <iostream>
#include <vector>

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 空间优化：使用一维数组
        std::vector<int> dp(n, 1); // 初始化第一行全为1

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                // 当前格的路径数 = 上方格的路径数 + 左方格的路径数
                // dp[j] 在更新前是上一行的值 (dp[i-1][j])
                // dp[j-1] 是当前行前一列的值 (dp[i][j-1])
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};

// int main() {
//     Solution sol;
//     std::cout << sol.uniquePaths(3, 7) << std::endl; // 输出: 28
//     return 0;
// }

简单多状态 DP

当单个状态无法完整描述问题时，需要定义多个状态。这类问题中，每个位置 i 可能处于不同的状态（例如，持有/不持有，接/不接），需要用多个 dp 数组或 dp 数组的多个维度来表示。

• 状态定义：dp[i][state] 表示在位置 i 处于 state 状态时的最优值。例如，f[i] 表示在 i 处进行某操作的最优值，g[i] 表示在 i 处不进行该操作的最优值。
• 状态转移方程：根据不同状态间的依赖关系分别建立转移方程。
• 初始化：根据问题的初始条件，初始化 dp 数组在 i=0 时的各个状态值。

经典例题：按摩师 (LeetCode 面试题 17.16)

一个按摩师不能接受相邻的预约。给定一个代表预约时长的数组，求能够获得的最长总预约时长。

C++ 优化代码 (状态压缩)

由于 dp[i] 只依赖于 dp[i-1]，可以将空间复杂度优化到 O(1)。

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int massage(std::vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        if (nums.size() == 1) {
            return nums[0];
        }

        // f: 接受当前预约的最大时长
        // g: 不接受当前预约的最大时长
        int g = 0, f = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            int temp_g = std::max(f, g); // 新的g[i]
            int temp_f = g + nums[i];   // 新的f[i]
            g = temp_g;
            f = temp_f;
        }

        return std::max(f, g);
    }
};

// int main() {
//     Solution sol;
//     std::vector<int> nums = {2, 7, 9, 3, 1};
//     std::cout << sol.massage(nums) << std::endl; // 输出: 12
//     return 0;
// }

子数组/子串系列

子数组或子串问题要求处理连续的元素片段。

• 状态定义：dp[i] 通常表示以 nums[i] 结尾的子数组所具有的某种性质（如最大和、最大乘积）。
• 状态转移方程：dp[i] 的值通常与 dp[i-1] 和 nums[i] 本身有关。
• 返回值：最终结果不一定是 dp[n-1]，因为最大/最优的子数组可能在任何位置结束，所以需要在遍历过程中记录全局最优解。

经典例题：最大子数组和 (LeetCode 53)

找出一个具有最大和的连续子数组，并返回其最大和。

C++ 优化代码 (状态压缩)

dp[i] 的计算只依赖于 dp[i-1]，可以进行状态压缩。

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        if (nums.empty()) return 0;

        int max_so_far = nums[0];
        int current_max = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            // 状态转移：决定是“自立门户”还是“加入组织”
            // 如果前一个子数组的和是负数，则不如从当前元素开始重新计算
            current_max = std::max(nums[i], current_max + nums[i]);
            // 更新全局最大值
            max_so_far = std::max(max_so_far, current_max);
        }
        return max_so_far;
    }
};

// int main() {
//     Solution sol;
//     std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//     std::cout << sol.maxSubArray(nums) << std::endl; // 输出: 6
//     return 0;
// }

子序列问题

子序列问题与子数组不同，它处理的元素不要求连续。

• 状态定义：dp[i] 通常表示以 nums[i] 结尾的子序列所具有的性质（例如，最长递增子序列的长度）。
• 状态转移方程：dp[i] 的计算通常需要遍历 j 从 0 到 i-1 的所有 dp[j]，找出满足条件的 dp[j] 来更新 dp[i]。
• 初始化：通常将 dp 数组的所有元素初始化为一个基本值（如 1）。

经典例题：最长递增子序列 (LeetCode 300)

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

C++ 优化代码 (贪心 + 二分查找)

此题存在一个更优的解法，时间复杂度为 O(NlogN)。维护一个“耐心排序”的 tails 数组，tails[i] 存储长度为 i+1 的所有递增子序列中末尾元素的最小值。

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> tails;
        tails.push_back(nums[0]);

        for (size_t i = 1; i < nums.size(); ++i) {
            if (nums[i] > tails.back()) {
                // 如果当前元素比所有已知递增子序列的末尾都大，
                // 它可以扩展最长的那个序列，形成一个更长的序列。
                tails.push_back(nums[i]);
            } else {
                // 否则，在 tails 数组中找到第一个大于或等于 nums[i] 的元素，
                // 并用 nums[i] 替换它。这表示我们找到了一个长度相同但末尾更小的递增子序列。
                auto it = std::lower_bound(tails.begin(), tails.end(), nums[i]);
                *it = nums[i];
            }
        }
        return tails.size();
    }
};

// int main() {
//     Solution sol;
//     std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
//     std::cout << sol.lengthOfLIS(nums) << std::endl; // 输出: 4
//     return 0;
// }

回文串问题

回文串问题关注字符串中正读和反读都相同的子串或子序列。

• 状态定义：通常使用二维 dp 数组，dp[i][j] 表示字符串 s 中从索引 i到 j 的子串 s[i...j] 是否为回文串。
• 状态转移方程：dp[i][j] 的真假取决于 s[i] == s[j] 以及 dp[i+1][j-1] 是否为真。
• 填表顺序：由于 dp[i][j] 依赖于 dp[i+1][j-1]（左下角的值），遍历时需要保证左下角的值先被计算。通常采用从下到上、从左到右的遍历顺序。

经典例题：最长回文子串 (LeetCode 5)

找到一个字符串中最长的回文子串。

C++ 优化代码 (中心扩展法)

动态规划的空间和时间复杂度均为 O(N2)。中心扩展法空间复杂度更优，为 O(1)。它以每个字符或两个字符之间为中心，向两边扩展，寻找最长的回文串。

C++

#include <iostream>
#include <string>
#include <algorithm>

class Solution {
public:
    std::string longestPalindrome(std::string s) {
        if (s.length() < 1) return "";
        int start = 0, max_len = 1;

        for (int i = 0; i < s.length(); ++i) {
            // 奇数长度的回文串
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度的回文串
            int len2 = expandAroundCenter(s, i, i + 1);
            
            int len = std::max(len1, len2);
            if (len > max_len) {
                start = i - (len - 1) / 2;
                max_len = len;
            }
        }
        return s.substr(start, max_len);
    }

private:
    int expandAroundCenter(const std::string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
};

// int main() {
//     Solution sol;
//     std::cout << sol.longestPalindrome("babad") << std::endl; // 输出: "bab" 或 "aba"
//     return 0;
// }

两个数组的 DP 问题

这类问题涉及两个输入数组（或字符串），状态定义需要同时考虑两个数组的索引。

• 状态定义：dp[i][j] 表示第一个数组的前 i 个元素和第二个数组的前 j 个元素之间的某种关系（如最长公共子序列长度）。
• 状态转移方程：dp[i][j] 的计算通常依赖于 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1]。
• 初始化：通常需要处理一个或两个数组为空的情况，这可以通过扩展 dp 表的大小（增加一行一列）来简化。

经典例题：最长公共子序列 (LeetCode 1143)

返回两个字符串的最长公共子序列的长度。

C++ 优化代码 (空间优化)

dp[i][j] 的计算只依赖于上一行和当前行的数据，可以将空间复杂度从 O(MN) 优化到 O(min(M,N))。

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

class Solution {
public:
    int longestCommonSubsequence(std::string text1, std::string text2) {
        int m = text1.length();
        int n = text2.length();

        // 确保 dp 数组大小为较小维度，节省空间
        if (m < n) {
            return longestCommonSubsequence(text2, text1);
        }

        std::vector<int> dp(n + 1, 0);

        for (int i = 1; i <= m; ++i) {
            int prev_row_prev_col = 0; // 模拟 dp[i-1][j-1]
            for (int j = 1; j <= n; ++j) {
                int temp = dp[j]; // 临时保存 dp[i-1][j]
                if (text1[i - 1] == text2[j - 1]) {
                    dp[j] = prev_row_prev_col + 1;
                } else {
                    dp[j] = std::max(dp[j], dp[j - 1]);
                }
                prev_row_prev_col = temp;
            }
        }
        return dp[n];
    }
};

// int main() {
//     Solution sol;
//     std::cout << sol.longestCommonSubsequence("abcde", "ace") << std::endl; // 输出: 3
//     return 0;
// }

0/1 背包问题

给定一组物品，每个物品只有一个，有各自的重量和价值。在限定的总重量内，如何选择物品使得总价值最高。

• 状态定义：dp[i][j] 表示从前 i 个物品中选择，放入容量为 j 的背包中所能获得的最大价值。
• 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])。这代表两种决策：不放第 i 个物品，或放第 i 个物品。

经典例题：分割等和子集 (LeetCode 416)

判断一个只包含正整数的非空数组是否可以被分割成两个子集，使得两个子集的元素和相等。这可以转化为一个 0/1 背包问题：能否从数组中选出一些数，其和恰好等于数组总和的一半。

C++ 优化代码 (空间优化)

可以将 dp 数组压缩到一维。关键在于内层循环必须从后往前遍历，以保证在计算 dp[j] 时，所依赖的 dp[j - weight[i]] 仍然是上一轮（i-1）的状态。

C++

#include <iostream>
#include <vector>
#include <numeric>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false;
        int target = sum / 2;

        std::vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                // dp[j] = dp[j] (不选num) || dp[j - num] (选num)
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }
};

// int main() {
//     Solution sol;
//     std::vector<int> nums = {1, 5, 11, 5};
//     std::cout << std::boolalpha << sol.canPartition(nums) << std::endl; // 输出: true
//     return 0;
// }

完全背包问题

与 0/1 背包不同，完全背包问题中的每种物品可以无限次地选取。

• 状态定义：同 0/1 背包。
• 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i]] + value[i])。注意，第二个选项是 dp[i] 而非 dp[i-1]，这表示在考虑第 i 个物品时，我们可以在已经放过第 i 个物品的背包中继续放。

经典例题：零钱兑换 (LeetCode 322)

给你一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。

C++ 优化代码 (空间优化)

同样可以压缩到一维。与 0/1 背包不同的是，内层循环必须从前往后遍历，以确保 dp[j - coin] 是本轮（i）更新过的值，这恰好体现了物品可重复选取的特性。

C++

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int coinChange(std::vector<int>& coins, int amount) {
        int max_val = amount + 1;
        std::vector<int> dp(amount + 1, max_val);
        dp[0] = 0;

        for (int coin : coins) {
            for (int j = coin; j <= amount; ++j) {
                dp[j] = std::min(dp[j], dp[j - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
};

// int main() {
//     Solution sol;
//     std::vector<int> coins = {1, 2, 5};
//     std::cout << sol.coinChange(coins, 11) << std::endl; // 输出: 3
//     return 0;
// }