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];全部评论 (0)
还没有任何评论哟~