今天学习了《动态规划》这一课
动态规划是运筹学的一个分支，是求解“决策过程最优值”问题的一种重要方法，在数学、计算机科学和经济学中应用广泛。
和分治法一样，动态规划也是通过把一个复杂的问题分解为相对简单的子问题的方式求解，再组合出答案的方法
以下是一道题的代码

include

include

include

include

include

include

using namespace std;
const int N = 1e6 + 10;
int n, a[N];
int dp[N][4][2];
int main() {
memset(dp, -0x3f3f3f3f, sizeof(dp));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
dp[0][0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j = 1)
dp[i][j][1] = max(dp[i][j][1],
max(dp[i – 1][j – 1][0], dp[i – 1][j – 1][1]) + a[i]);
}
}
printf("%d\n", max(dp[n][3][0], dp[n][3][1]));
return 0;
}

动态规划有一定的难度，状态转移方程是非常重要的，如果把状态转移方程写出来了，那做出题目也非常简单了