一：零钱兑换

image-20251019170809648

1. 记忆化搜索

本质上属于迭代，找出子目标数据的最小值，自顶向下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> count;
    int coinChange(vector<int>& coins, int amount) {
        count.resize(amount);
        return recursion(coins, amount);
    }
    int recursion(vector<int>& coins, int amount)
    {
        if (amount == 0) return 0;
        if (amount < 0) return -1;
        if (count[amount - 1] != 0) return count[amount - 1];
        int minNum = INT_MAX;
        for (auto& coin : coins)
        {
            int temp = recursion(coins, amount - coin);
            if (temp >= 0 && temp < minNum)
                minNum = temp + 1;
        }
        count[amount - 1] = minNum == INT_MAX ? -1 : minNum;
        return count[amount - 1];
    }
};

image-20251019155847908

2. 动态规划

使用动态规划的关键点在于找出状态转移方程，该题目可求出当前硬币对应的上一个目标值的最小硬币数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int max = amount + 1;      // 不能使用INT_MAX，见下
        vector<int> count(amount + 1, max);     // 这里使用+1把0也算入
        count[0] = 0;
        for (int i = 1; i <= amount; ++i)
        {
            for (auto& coin : coins)
            {
                if (coin <= i)
                {
                    count[i] = min(count[i], count[i - coin] + 1);      // INT_MAX这里会超出范围
                }
            }
        }
        return count[amount] = count[amount] == amount + 1 ? -1 : count[amount];
    }
};

image-20251019155858537

二：单词拆分

image-20251019170755866

1. 动态规划

假设当前位于x，对于0 ~ x的子串需要寻找一个位置 j，使0 ~ j位于给定数组中，然后再判断j + 1 ~ x是否位于数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hashWord;
        int len = s.size();
        for (auto& word : wordDict) hashWord.insert(word);
        vector<bool> dp(len + 1);
        dp[0] = true;
        for (int i = 1; i <= len; ++i)
            for (int j = 0; j < i; ++j)
                if (dp[j] && hashWord.find(s.substr(j, i - j)) != hashWord.end())
                {
                    dp[i] = true;
                    break;
                }
        return dp[len];
    }
};

image-20251019155824529

三：最长递增子序列

image-20251019170833781

1. 动态规划

使用一个数组来记录以给定数组的每个元素结尾的子序列的长度，如果当前值大于某个最长子序列的最后一个值，则把它加入

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        vector<int> dp(len, 1);
        for (int i = 0; i < len; ++i)
            for (int j = 0; j < i; ++j)
                if (nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
        return *max_element(dp.begin(), dp.end());
    }
};

image-20251019155807347

2. 贪心+二分查找

使用一个数组来维护最长子序列的最后一个值，如果下个值大于最后一个值则加入，如果不大于则替换数组中首个大于该元素的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        int size = 1;
        vector<int> dp(len + 1, 0);
        dp[size] = nums[0];
        for (int i = 1; i < len; ++i)
        {
            if (nums[i] > dp[size])
                dp[++size] = nums[i];
            else
            {
                int left = 1, right = size;
                int pos = 0;
                while (left <= right)
                {
                    int mid = (left + right) >> 1;
                    if (dp[mid] < nums[i])
                    {
                        pos = mid;
                        left = mid + 1;
                    } else
                        right = mid - 1;
                }
                dp[pos + 1] = nums[i];
            }
        }
        return size;
    }
};

image-20251019155758598