动态规划的两个重要步骤：

一、状态设计

二、状态转移方程

例

数字三角形：一只蚂蚁从n级数字三角形顶部走到底部，请找到这条路线，使走过的数字总和最大。

1.状态设计：f[i][j]表示i级第j个数字以下数字总和最大值

2.状态转移方程：f[i][j] = a[i][j] +max(f[i+1][j]+f[i+1][j+1])

转移方法：从下到上，从左向右转移

for(i=n;i;i--){
    for(j=1;j<=i;j++){
　　　　　　　if(i==n) f[i][j]=a[i][j];
            else f[i][j] = max(f[i+1][j+1]+f[i+1][j])+a[i][j];
     }
}

---

另一种方式：记忆化搜索（DFS）

·保证每个状态只被访问一次！

int dfs(int x,int y){
    if(x==n) return a[x][y];
    if(vis[x][y]) return f[x][y];//已被访问，f所存储为正确值
    vis[x][y] = 1; //记忆数组，避免重复搜索！
    return f[x][y] = a[x][y] + max(dfs(x+1,y),dfs(x+1,y+1)); //存储数组进行存储
}