DP第一场.ppt

文档介绍：DP 第一场
1
一. 数字三角形
2
1. 问题描述
3
2. 能否贪心?
4
3. 递归求解
int try(int i, int j)
{
if(i==n)
{
return a[i][j];
}
else
{
return max(try(i+1,j), try(i+1,j+1)) + a[i][j];
}
}
5
4. 递归直接求解存在的问题
6
5. 记忆化求解
int solve(int i, int j)
{
if(dp[i][j] >= 0)
{
return dp[i][j];
}
else if(i == n)
{
return dp[i][j] = a[i][j];
}
else
{
return dp[i][j] = max(solve(i+1,j), solve(i+1,j+1)) + a[i][j];
}
}
7
6. 课后练****br/>利用记忆化求解斐波那契数列第45项?
8
7. 递推计算(动态规划)
for(j=1; j<=n; j++)
dp[n][j] = a[n][j];
for(i=n-1; i>=1; i--)
for(j=1; j<=i; j++)
dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
9
8. DP解题思路
(1)找子问题
dp[i][j]:a[i][j]到第n层的最大值。
(2)自顶向下分析,自底向上求解。注意边界。
(3)DP的有效性:重叠子问题
(4)DP vs 分治 vs 贪心
(5)最优子结构(最优化原理):一个最优化策略的子策略总是最优的。
(6)不满足最优子结构则无法利用dp求解,为什么?
10