动态规划的核心思想是利用子问题的解来构建整个问题的解。为此,我们通常使用一个表格或数组来存储子问题的解,以便在需要时进行查找和使用。
1.最大字段和
#include <iostream>
using namespace std;
#define M 200000int 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)