动态规划（DP）课堂笔记

一、动态规划核心思想

1. 问题背景

若直接枚举从起点到终点的所有方案数，会因情况过多导致超时。DP思想通过记录「某一状态的最优结果」，避免重复计算，高效解决有限集合的优化问题。

2. 三大核心性质

• 无后效性：当前状态仅由之前的状态推导而来，不影响未来状态。
• 最优子结构：dp数组记录的状态结果一定是最优的，大问题的最优解由子问题的最优解组合而成。
• 子问题重叠：递推解决的是同一类问题（仅规模不同），通过记录子问题结果避免重复计算。

二、经典DP问题模型

1. 换硬币问题（引入示例）

• 问题描述：有n元钱，硬币面值为1, 6, 7, 10元，求换硬币的最优方案（如最少硬币数）。
• DP作用：通过状态记录避免枚举所有组合，高效求解。

2. 回文子串计数

问题描述

统计字符串中所有回文子串的数量。

状态定义

dp[l][r]：表示字符串从第l个字母到第r个字母是否为回文子串（1是，0否）。

状态转移方程

若 s[l] == s[r] 且 dp[l+1][r-1] == 1，则 dp[l][r] = 1。

初始化

• 长度为1的子串：dp[i][i] = 1（每个字符自身是回文）。
• 长度为2的子串：若 s[i] == s[i+1]，则 dp[i][i+1] = 1。

代码实现

#include<bits/stdc++.h>
using namespace std;

bool dp[2010][2010]; // dp[l][r]：s[l..r]是否为回文子串
int n, ans;
string s;

int main() {
    cin >> n >> s;
    s = "@" + s + "@"; // 下标从1开始，方便处理

    // 初始化长度1和2的回文子串
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 1;
        ans += dp[i][i]; // 累加长度1的回文
        if (i + 1 <= n && s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
            ans += dp[i][i + 1]; // 累加长度2的回文
        }
    }

    // 枚举长度≥3的子串
    for (int len = 3; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            // 状态转移：两端字符相等+内部子串是回文
            dp[l][r] = (s[l] == s[r] && dp[l + 1][r - 1]);
            ans += dp[l][r]; // 累加当前回文子串
        }
    }

    cout << ans;
    return 0;
}

3. 最大/最小子段和

（1）最大子段和

• 状态定义：dp[i]表示以第i个数结尾的最大子段和。
• 状态转移方程： dp[i] = max(dp[i - 1], 0) + a[i] （若前一个子段和为负，则重新开始以a[i]为子段）
• 结果计算：max(dp[1], dp[2], ..., dp[n])

（2）最小子段和

• 状态转移方程： dp[i] = min(dp[i - 1], 0) + a[i]

4. 打家劫舍问题

• 问题描述：一排店铺，偷第i家则不能偷第i-1家，求能偷到的最大价值。
• 状态定义：dp[i]表示前i家店铺能偷到的最大价值。
• 状态转移方程： dp[i] = max(dp[i - 2] + a[i], dp[i - 1]) （两种决策：偷第i家（加dp[i-2]），或不偷第i家（取dp[i-1]））
• 初始化：dp[1] = a[1]

5. 乘积正负子区间计数

• 问题描述：统计数组中「乘积为负」和「乘积为正」的连续子区间个数。
• 状态定义：
  • dp[i]：以第i个数结尾的、乘积为负的连续子区间个数。
  • dp2[i]：以第i个数结尾的、乘积为正的连续子区间个数。
• 结果计算：
  • 乘积为负的总个数：dp[1] + dp[2] + ... + dp[n]
  • 乘积为正的总个数：dp2[1] + dp2[2] + ... + dp2[n]

6. 最长上升子序列（LIS）

• 问题描述：求数组中最长的严格上升子序列的长度。
• 状态定义：dp[i]表示以第i个数结尾的最长上升子序列长度。
• 状态转移方程： dp[i] = max(dp[j] + 1) （需满足 j < i 且 a[i] > a[j]） （遍历i之前的所有j，若a[i]更大，则尝试更新dp[i]）