POJ 1163 求数字三角形由顶到底边的最大数字和 动态规划

这题是求数字三角形由顶到底边最大数字和对应的路径，在准备夏令营的时候红皮教材上面有，当时没有学动态规划算法，不是很理解，经过这一阵对算法的学习和POJ训练，总算在10分钟内独立思考AC，其实挺简单，满足最优子结构和无后效性，是经典的动态规划问题。

一般的思考方法是，由特殊情况比如题目给的示例数据入手，分析如何计算辅助数组dp的值，dp[i][j]记录以r[i][j]为顶点向下走到底边可以得到的最大和，dp数组底边的值就是数字三角形底边数字，然后从底向上计算，dp数组的计算方程（即动态规划状态方程）为

dp[i][j] = max(r[i][j] + dp[i+1][j] , r[i][j] + dp[i+1][j+1])

可以进一步化简就是 dp[i][j] = r[i][j] + max(dp[i+1][j] , dp[i+1][j+1]);

题目所求为dp[0][0]

Source Code

Problem: 1163		User: yangliuACMer
Memory: 324K		Time: 16MS
Language: C++		Result: Accepted

//16:09
#include <iostream>
using namespace std;

int max(int a,int b){
	return a>b?a:b;
}

int main(){
	int dp[101][101],r[101][101];
	int n,i,j;
	cin>>n;
	for(i = 0; i < n; i++){
		for(j = 0; j < i+1; j++){
			cin>>r[i][j];
		}
	}
	memset(dp,0,sizeof(dp));
	for(i = 0; i < n; i++){
		dp[n-1][i] = r[n-1][i];
	}
	for(i = n-2; i >= 0; i--){
		for(j = 0; j < i+1; j++){
			//dp[i][j] = max(r[i][j] + dp[i+1][j] , r[i][j] + dp[i+1][j+1]);//可以进一步化简
			dp[i][j] = r[i][j] + max(dp[i+1][j] , dp[i+1][j+1]);
		}
	}
	cout<<dp[0][0]<<endl;
	return 0;
}
//16:18