洛谷P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

洛谷P1216 数字三角形 Number Triangles

此题是一个很经典的动态规划题目，对刚入门的同学来说是一个很好的练习题目。如果熟悉了解回溯法的同学，你会立刻发现这是一个动态规划题。
思路：定义[i][j]为出发点时的能够得到的最大和，显然，在这个状态定义下，最大和的解为dp[1][1]。
状态转移：从[i][j]出发有两种决策.一种是往左走到[i+1][j]，此时需要求从[i+1][j]为出发点的最大和；同理向右走到[i+1][j+1],此时需要求从[i+1][j]为出发点的最大和。
得到状态转移方程为：

dp[i][j] = a[i][j] + max{dp[i+1][j],dp[i+1][j+1]}

状态方程得到，那么问题也就迎刃而解了。