动态规划习题

动态规划的核心思想是利用子问题的解来构建整个问题的解。为此，我们通常使用一个表格或数组来存储子问题的解，以便在需要时进行查找和使用。

1.最大字段和

#include <iostream>
using namespace std;
#define M 200000

int main()
{
    int n, a[M], dp[M];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[0] = a[0];
    int ans = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(a[i], dp[i - 1] + a[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2.装箱问题