C++：动态规划DP；_c++dp状态转移方程

动态规划：将子问题的解记录下来，（记忆花搜索）

从顶到底和最大的路径

状态：dp[i][j]

• 走左边
• 走右边

状态转移方程：

从边界开始（底开始），往上走，第[i][j]的状态就是最大的加上它自己。
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j]

//边界就是他自己
for (int j = 1; j <= N; j++)
{
	dp[N][j] = f[N][j];
}

//从倒数第二层开始
for (int i = N - 1; i >= 1; i--)
{
	for (int j = 1; j <= i; j++) {
		dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
	}
}

cout << dp[1][1];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6
-2 11 -4 13 -5 -2

连续最大子序列和：到A[i]的值最大

状态：dp[i]

• 自己就是最大
• 前面加上自己是最大

状态转移方程：

从第一个开始：第i个的状态就是(自己）或者自己加上前面的。
dp[i] = max(dp[i], dp[i - 1] + f[i]);

void dynamicd()
{
	memset(dp, 0, sizeof(dp));
	int maxdp = 0;
	for (int i = 0; i < N; i++)
	{
		dp[i] = max(dp[i], dp[i - 1] + f[i]);
		if (dp[i] > maxdp)maxdp = dp[i];
	}
	cout << maxdp;
}
1
2
3
4
5
6
7
8
9
10
11

最长非递减子序列(可以不连续