数塔问题 简单dp

自上而下

//对应正上方和斜前上方
//num存的是数塔
dp[0][0] = num[0][0];
for (int i = 1; i < n; i++)
{
	dp[i][0] = dp[i - 1][0] + num[i][0];
	for (int j = 1; j <= i; j++)
	{
		dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[i][j];
	}
}
sort(dp[n - 1], dp[n - 1] + n,cmp);
printf("%d\n", dp[n-1][0]);

自下而上

//数组中和它相邻的是它正对下方和斜右下方
for (int i = 0; i < n; i++)
	dp[n - 1][i] = num[n - 1][i];
for (int i = n - 2; i >= 0; i--)
{
	for (int j = 0; j <= i; j++)
		dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + num[i][j];
}
printf("%d\n", dp[0][0]);