1
// 例：斐波那契数列 F(n) = F(n-1) + F(n-2), F(1)=F(2)=1
2

3
// 方法一：记忆化搜索（Top-Down）
4
// 从大问题出发，递归求解，用缓存避免重复计算
5
int fib_memo(int n, std::vector<int>& memo) {
6
    if (n <= 2) return 1;
7
    if (memo[n] != 0) return memo[n];
8
    return memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
9
}
10

11
// 方法二：递推（Bottom-Up）
12
// 从最小的子问题开始，逐步向上构建
13
int fib_dp(int n) {
14
    if (n <= 2) return 1;
15
    int prev2 = 1, prev1 = 1;
16
    for (int i = 3; i <= n; ++i) {
17
        int curr = prev1 + prev2;
18
        prev2 = prev1;
19
        prev1 = curr;
20
    }
21
    return prev1;
22
}

1
// 零钱兑换 (LeetCode 322): 用最少的硬币凑出 amount
2
// 每种硬币无限次 → 完全背包
3
int coinChange(std::vector<int>& coins, int amount) {
4
    // dp[j] = 凑出金额 j 所需的最少硬币数
5
    std::vector<int> dp(amount + 1, amount + 1);  // amount+1 表示"不可能"
6
    dp[0] = 0;
7

8
    // 外层遍历硬币，内层正序遍历金额 → 每种硬币可以多次使用
9
    for (int coin : coins) {
10
        for (int j = coin; j <= amount; ++j) {
11
            dp[j] = std::min(dp[j], dp[j - coin] + 1);
12
        }
13
    }
14
    return dp[amount] > amount ? -1 : dp[amount];
15
}

1
// LCS 的 DP 表：dp[i][j] 依赖 左、上、左上
2
// 两种遍历顺序在正确性上等价，但性能差巨大：
3

4
int n = 5000;
5
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
6

7
// ✅ 行优先：内层循环遍历列，连续访问内存
8
for (int i = 1; i <= n; ++i) {
9
    for (int j = 1; j <= n; ++j) {   // ⭐ 连续访问 dp[i][j]
10
        dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
11
    }
12
}
13
// 每次访问 dp[i][j] 和 dp[i][j-1] 位于同一 cache line → 命中率高
14

15
// ❌ 列优先：内层循环遍历行，跳跃访问内存
16
for (int j = 1; j <= n; ++j) {
17
    for (int i = 1; i <= n; ++i) {   // ⭐ 跳跃访问不同行的同一列
18
        dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
19
    }
20
}
21
// dp[i][j] 和 dp[i+1][j] 在内存中相距一整行 → 几乎每次 cache miss

1
// LCS 滚动数组优化（只用两行）
2
int longestCommonSubsequence_roll(std::string text1, std::string text2) {
3
    int m = text1.size(), n = text2.size();
4
    std::vector<std::vector<int>> dp(2, std::vector<int>(n + 1, 0));
5

6
    for (int i = 1; i <= m; ++i) {
7
        int cur = i % 2;
8
        int prev = 1 - cur;
9
        for (int j = 1; j <= n; ++j) {
10
            if (text1[i - 1] == text2[j - 1]) {
11
                dp[cur][j] = dp[prev][j - 1] + 1;
12
            } else {
13
                dp[cur][j] = std::max(dp[prev][j], dp[cur][j - 1]);
14
            }
15
        }
16
    }
17
    return dp[m % 2][n];
18
}

1
// 区间 DP 入门（虽然本章是线性 DP，但这道题在面试中常和 LCS/LIS 放一起考）
2
// dp[i][j] = s[i..j] 是否是回文串
3
// 转移：s[i]==s[j] 且 (j-i<2 或 dp[i+1][j-1])
4
std::string longestPalindrome(std::string s) {
5
    int n = s.size();
6
    if (n < 2) return s;
7

8
    std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
9
    int start = 0, maxLen = 1;
10

11
    // 所有长度为 1 的都是回文
12
    for (int i = 0; i < n; ++i) dp[i][i] = true;
13

14
    // 按长度递增遍历（区间 DP 的标准遍历顺序）
15
    for (int len = 2; len <= n; ++len) {
16
        for (int i = 0; i + len - 1 < n; ++i) {
17
            int j = i + len - 1;
18
            if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1])) {
19
                dp[i][j] = true;
20
                if (len > maxLen) {
21
                    start = i;
22
                    maxLen = len;
23
                }
24
            }
25
        }
26
    }
27
    return s.substr(start, maxLen);
28
}

1
// dp[i] = s[0..i-1] 能否由 wordDict 中的单词拼接而成
2
// 转移：存在 j < i，使得 dp[j] 为 true 且 s[j..i-1] 在字典中
3
bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
4
    std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
5
    int n = s.size();
6

7
    std::vector<bool> dp(n + 1, false);
8
    dp[0] = true;  // 空前缀可以被拼接
9

10
    for (int i = 1; i <= n; ++i) {
11
        for (int j = 0; j < i; ++j) {
12
            if (dp[j] && dict.count(s.substr(j, i - j))) {
13
                dp[i] = true;
14
                break;  // 一旦找到一种拼接方式即可
15
            }
16
        }
17
    }
18
    return dp[n];
19
}

1
// dp[i][j] = s[0..i-1] 能否匹配 p[0..j-1]
2
// 关键：p[j-1] == '*' 时有两种选择：
3
//   - 不用 '*'（删除 p[j-2] 和 '*'）：dp[i][j-2]
4
//   - 用 '*'（匹配一个或多个）：s[i-1] 匹配 p[j-2] 且 dp[i-1][j]
5
bool isMatch(std::string s, std::string p) {
6
    int m = s.size(), n = p.size();
7
    std::vector<std::vector<bool>> dp(m + 1, std::vector<bool>(n + 1, false));
8
    dp[0][0] = true;
9

10
    // 处理空字符串匹配 a*, a*b*, ... 的情况
11
    for (int j = 2; j <= n; ++j) {
12
        if (p[j - 1] == '*') {
13
            dp[0][j] = dp[0][j - 2];  // '*' 可以消掉前一个字符
14
        }
15
    }
16

17
    for (int i = 1; i <= m; ++i) {
18
        for (int j = 1; j <= n; ++j) {
19
            if (p[j - 1] == '*') {
20
                // 不用 '*' : dp[i][j-2]
21
                // 用 '*' : s[i-1] 匹配 p[j-2] 且 dp[i-1][j]
22
                dp[i][j] = dp[i][j - 2] ||
23
                    (dp[i - 1][j] &&
24
                     (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
25
            } else {
26
                dp[i][j] = dp[i - 1][j - 1] &&
27
                    (s[i - 1] == p[j - 1] || p[j - 1] == '.');
28
            }
29
        }
30
    }
31
    return dp[m][n];
32
}

1
struct Equipment {
2
    std::string name;
3
    int         weight;       // 负重
4
    float       attackBonus;  // 攻击加成
5
    float       defenseBonus; // 防御加成
6
    // 综合评分 = 攻击 * 权重 + 防御 * 权重（玩家可调）
7
    float score(float attackWeight, float defenseWeight) const {
8
        return attackBonus * attackWeight + defenseBonus * defenseWeight;
9
    }
10
};
11

12
struct EquipmentSelection {
13
    int maxWeight;
14
    float totalScore;
15
    std::vector<int> selectedIndices;  // 选中的装备索引
16
};
17

18
EquipmentSelection optimizeEquipment(
19
    const std::vector<Equipment>& items,
20
    int maxWeight,
21
    float atkW = 1.0f, float defW = 1.0f) {
22

23
    int n = items.size();
24
    // dp[j] = 容量 j 时的最大评分
25
    std::vector<float> dp(maxWeight + 1, 0);
26
    // 回溯表：trace[i][j] = 在容量 j 时是否选了第 i 件
27
    std::vector<std::vector<bool>> trace(n, std::vector<bool>(maxWeight + 1, false));
28

29
    for (int i = 0; i < n; ++i) {
30
        float score = items[i].score(atkW, defW);
31
        for (int j = maxWeight; j >= items[i].weight; --j) {
32
            float newScore = dp[j - items[i].weight] + score;
33
            if (newScore > dp[j]) {
34
                dp[j] = newScore;
35
                trace[i][j] = true;
36
            }
37
        }
38
    }
39

40
    // 回溯：找出具体选了哪些装备
41
    EquipmentSelection result;
42
    result.maxWeight = maxWeight;
43
    result.totalScore = dp[maxWeight];
44

45
    int j = maxWeight;
46
    for (int i = n - 1; i >= 0; --i) {
47
        if (trace[i][j]) {
48
            result.selectedIndices.push_back(i);
49
            j -= items[i].weight;
50
        }
51
    }
52
    std::reverse(result.selectedIndices.begin(), result.selectedIndices.end());
53
    return result;
54
}

1
struct Skill {
2
    int  id;
3
    int  requiredPrev;   // 前置技能 ID（-1 表示无前置）
4
    int  damage;
5
    bool canFollow(int prevSkill) const {
6
        return requiredPrev == -1 || requiredPrev == prevSkill;
7
    }
8
};
9

10
// 在满足前置约束的条件下，找最长的有效连招序列
11
int longestCombo(const std::vector<Skill>& skills, const std::vector<int>& sequence) {
12
    int n = sequence.size();
13
    // dp[i] = 以 sequence[i] 结尾的最长有效连招长度
14
    std::vector<int> dp(n, 1);
15

16
    int maxLen = 1;
17
    for (int i = 1; i < n; ++i) {
18
        const Skill& cur = skills[sequence[i]];
19
        for (int j = 0; j < i; ++j) {
20
            const Skill& prev = skills[sequence[j]];
21
            if (cur.canFollow(prev.id)) {
22
                dp[i] = std::max(dp[i], dp[j] + 1);
23
            }
24
        }
25
        maxLen = std::max(maxLen, dp[i]);
26
    }
27
    return maxLen;
28
}

1
struct Consumable {
2
    std::string name;
3
    int         useTime;      // 使用所需时间（秒）
4
    float       healAmount;   // 回复量
5
    float       buffAmount;   // Buff 增益
6
};
7

8
float maxCombatEffectiveness(
9
    const std::vector<Consumable>& items,
10
    int totalTime) {
11

12
    // dp[t] = 在 t 秒内能获得的最大战斗收益
13
    std::vector<float> dp(totalTime + 1, 0);
14

15
    for (const auto& item : items) {
16
        float value = item.healAmount * 0.6f + item.buffAmount * 0.4f;
17
        for (int t = item.useTime; t <= totalTime; ++t) {  // 正序：无限使用
18
            dp[t] = std::max(dp[t], dp[t - item.useTime] + value);
19
        }
20
    }
21
    return dp[totalTime];
22
}

1
#include <string>
2
#include <vector>
3
#include <algorithm>
4

5
class SpellChecker {
6
    std::vector<std::string> _dictionary;
7

8
public:
9
    void loadDictionary(const std::vector<std::string>& words) {
10
        _dictionary = words;
11
    }
12

13
    // 找编辑距离最小的 topK 个候选词
14
    std::vector<std::string> suggest(const std::string& input, int topK = 3) {
15
        std::vector<std::pair<int, std::string>> candidates;
16

17
        for (const auto& word : _dictionary) {
18
            int dist = editDistance(input, word);
19
            candidates.push_back({dist, word});
20
        }
21

22
        std::partial_sort(candidates.begin(),
23
                          candidates.begin() + std::min(topK, (int)candidates.size()),
24
                          candidates.end());
25

26
        std::vector<std::string> result;
27
        for (int i = 0; i < std::min(topK, (int)candidates.size()); ++i) {
28
            result.push_back(candidates[i].second);
29
        }
30
        return result;
31
    }
32

33
private:
34
    // 滚动数组优化版编辑距离：O(min(m,n)) 空间
35
    int editDistance(const std::string& a, const std::string& b) {
36
        // 确保 a 是较短的串
37
        if (a.size() > b.size()) return editDistance(b, a);
38

39
        int m = a.size(), n = b.size();
40
        std::vector<int> dp(m + 1);
41
        std::iota(dp.begin(), dp.end(), 0);  // dp[i] = i
42

43
        for (int j = 1; j <= n; ++j) {
44
            int prev = dp[0];  // 左上角的值
45
            dp[0] = j;         // 第一列
46
            for (int i = 1; i <= m; ++i) {
47
                int temp = dp[i];
48
                if (a[i - 1] == b[j - 1]) {
49
                    dp[i] = prev;
50
                } else {
51
                    dp[i] = 1 + std::min({dp[i], dp[i - 1], prev});
52
                }
53
                prev = temp;
54
            }
55
        }
56
        return dp[m];
57
    }
58
};