凑零钱

这同样也是一个经典的动态规划问题，比如我们要凑22元，那么一共由三个子问题（即有三种情况可以一步凑到22元）：1、22+1  2、17＋5、 3、11+11 

这三个子问题的最小值，就是凑到22元所需要的最小组合。

因此，我们可以维护一数组dp[n]，表示n块钱最少需要几张钱币来凑出，当n＞=11时，dp[n]可以表示为：

我们用伪代码总结一下：

1. 状态定义：dp[i] 表示 “凑出 i 元所需的最少硬币数量”。
2. 初始化：
   • dp[0] = 0（凑 0 元不需要硬币）；
   • 对于 i ≥ 1，先初始化 dp[i] = i（默认全用 1 元硬币，最多需要 i 张）。
3. 状态转移：对每个金额 i，尝试用 1 元、5 元、11 元硬币更新最少数量：
   • 若用 1 元：dp[i] = min(dp[i], dp[i-1] + 1)（先凑 i-1 元，再加 1 张 1 元）；
   • 若用 5 元：dp[i] = min(dp[i], dp[i-5] + 1)（先凑 i-5 元，再加 1 张 5 元）；
   • 若用 11 元：dp[i] = min(dp[i], dp[i-11] + 1)（先凑 i-11 元，再加 1 张 11 元）。

代码如下：

#include <bits/stdc++.h>
#include <vector>
#include <algorithm> // 用于min函数

using namespace std;

int main() {
    int n;
    cin >> n;
    // 定义dp数组，大小为n+1（覆盖0~n元）
    vector<int> dp(n + 1);
    
    // 初始化：dp[0]为0（凑0元不需要硬币）
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        // 初始默认全用1元，最多需要i张
        dp[i] = i;
        // 尝试用1元硬币更新
        if (i >= 1) {
            dp[i] = min(dp[i], dp[i - 1] + 1);
        }
        // 尝试用5元硬币更新
        if (i >= 5) {
            dp[i] = min(dp[i], dp[i - 5] + 1);
        }
        // 尝试用11元硬币更新
        if (i >= 11) {
            dp[i] = min(dp[i], dp[i - 11] + 1);
        }
    }
    
    // 输出凑n元所需的最少硬币数
    cout << dp[n] << endl;
    return 0;
}

最长上升子序列

同样的，我们来思考如何维护dp[n]（其表示以n位置的数字结尾的最长上升子序列）

我们来看一个更有代表性的序列：10、9、2、5、3、7、22、18

• 以 10（dp[0]）结尾：无前置元素，dp[0] = 1；
• 以 9（dp[1]）结尾：前面的 10 > 9（不满足递增），无有效前置元素，dp[1] = 1；
• 以 2（dp[2]）结尾：前面的 10、9 都 > 2（不满足递增），无有效前置元素，dp[2] = 1；
• 以 5（dp[3]）结尾：前面只有 2 < 5（有效前置元素j=2），因此dp[3] = dp[2] + 1 = 2（子序列：2、5）；
• 以 3（dp[4]）结尾：前面只有 2 < 3（有效前置元素j=2），因此dp[4] = dp[2] + 1 = 2（子序列：2、3）；
• 以 7（dp[5]）结尾：前面比 7 小的元素有 2（j=2，dp=1）、5（j=3，dp=2）、3（j=4，dp=2），其中最大dp[j]为 2，因此dp[5] = 2 + 1 = 3（子序列：2、5、7 或 2、3、7）；
• 以 22（dp[6]）结尾：前面所有元素（10、9、2、5、3、7）都 < 22，对应的dp[j]分别为 1、1、1、2、2、3，其中最大dp[j]为 3，因此dp[6] = 3 + 1 = 4（子序列：2、5、7、22 或 2、3、7、22）；
• 以 18（dp[7]）结尾：前面比 18 小的元素有 10、9、2、5、3、7（22 > 18，不满足递增，排除），对应的dp[j]分别为 1、1、1、2、2、3，其中最大dp[j]为 3，因此dp[7] = 3 + 1 = 4（子序列：2、5、7、18 或 2、3、7、18）；

一般性规则：

若以元素a（对应dp[n]）结尾，需找到所有在a之前且比a小的元素（设这些元素对应位置为k），则dp[n] = max(dp[k] for all valid k) + 1；若没有这样的k（即a比前面所有元素都小），则dp[n] = 1。

因此，编写伪代码如下：

• 1、状态定义：dp[i] 表示 “以第i个元素结尾的最长上升子序列的长度”。
• 2、初始化：每个元素自身是长度为 1 的子序列，因此dp[i] = 1。
• 3、状态转移：对每个i，遍历前面的所有元素j（j < i），若nums[i] > nums[j]，则dp[i] = max(dp[i], dp[j]+1)（即把nums[i]接在以nums[j]结尾的子序列后面）。
• 4、结果：遍历dp数组，取最大值即为最长上升子序列的长度。

代码如下：

#include <bits/stdc++>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    vector<int> dp(n, 1); // 每个元素至少是长度为1的子序列
    int max_len = 1;      // 记录最长长度

    for (int i = 1; i < n; ++i) {
        // 遍历i之前的所有元素j
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]); // 更新最长长度
    }

    cout << max_len << endl;
    return 0;
}

最大字段和

序列为：nums = [2, -4, 3, -1, 2, -4, 3]（索引 0~6），我们定义 dp[i] 表示 “以第i个元素结尾的最大连续子段和”，并维护变量flag记录全局最大子段和。

1. 以 2（nums[0]）结尾：这是序列第一个元素，无前置子段，因此 dp[0] = 2。此时全局最大子段和 flag = 2。

2. 以 - 4（nums[1]）结尾：需判断 “单独选 - 4” 和 “接在前面的子段后（2 + (-4)）” 哪个和更大：dp[1] = max(-4, dp[0] + (-4)) = max(-4, 2-4=-2) = -2。此时flag仍为 2（-2 < 2）。

3. 以 3（nums[2]）结尾：判断 “单独选 3” 和 “接在前面的子段后（-2 + 3）” 哪个和更大：dp[2] = max(3, dp[1] + 3) = max(3, -2+3=1) = 3。此时flag更新为 3（3 > 2）。

4. 以 - 1（nums[3]）结尾：判断 “单独选 - 1” 和 “接在前面的子段后（3 + (-1)）” 哪个和更大：dp[3] = max(-1, dp[2] + (-1)) = max(-1, 3-1=2) = 2。此时flag仍为 3（2 < 3）。

5. 以 2（nums[4]）结尾：判断 “单独选 2” 和 “接在前面的子段后（2 + 2）” 哪个和更大：dp[4] = max(2, dp[3] + 2) = max(2, 2+2=4) = 4。此时flag更新为 4（4 > 3）。

6. 以 - 4（nums[5]）结尾：判断 “单独选 - 4” 和 “接在前面的子段后（4 + (-4)）” 哪个和更大：dp[5] = max(-4, dp[4] + (-4)) = max(-4, 4-4=0) = 0。此时flag仍为 4（0 < 4）。

7. 以 3（nums[6]）结尾：判断 “单独选 3” 和 “接在前面的子段后（0 + 3）” 哪个和更大：dp[6] = max(3, dp[5] + 3) = max(3, 0+3=3) = 3。此时flag仍为 4（3 < 4）。

一般性规则：

1. 状态定义：dp[i]表示 “以第i个元素结尾的最大连续子段和”。
2. 状态转移：对每个元素nums[i]，dp[i] = max(nums[i], dp[i-1] + nums[i])（要么单独选当前元素，要么将当前元素接在前面的最大子段后）。
3. 全局最大值：维护一个变量（如flag），遍历每个dp[i]，不断更新flag为 “当前flag与dp[i]的较大值”。
4. 边界条件：若序列只有一个元素，最大子段和就是该元素本身；若序列全为负数，最大子段和为其中最大的那个元素（因子段需非空）。

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

int n;
long long dp[300000], nums[300000];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    long long flag = nums[0];
    dp[0] = flag;
    for(int i = 1; i < n; i++)
    {
        dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        if(flag < dp[i]) flag = dp[i];
    }
    cout << flag;
}

这里用long long主要是为了通过测试点，不然int求和有可能溢出（或者取mod也可以，但是这个题没给）。

总结

动态规划问题的核心，就在于如何维护记录子问题的数据结构dp（通过状态转移方程），我们需要先明确dp的定义（作用），如何初始化，根据题目来找出状态是如何转移的（如何从dp[j]到dp[i]，j＜i）。

最后还有一个数字三角形的问题，需要维护一个二维数组dp，状态转移方程很容易观察出。留给大家练习。