数字三角问题
有一个由非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如图：
从第一行的数开始，每一次可以往左下或右下走一格，知道走到最下行，把沿途经过的数全部加起来，如何走才能使得到的这个和尽量大？分析
- 采用(dfs)暴搜每次把每个点能经过的路线全部找出，但是对于(n)层 数字三角形的完整路线有(2^{n-1})条，当(n)很大时，(dfs)是定不行的。 (dfs)会超时，那有什么好方法呢？
- 把当前的位置((i,j))看成一个状态，(d(i,j))表示的是从格子((i,j))出发能取到的最大和(包括((i,j))本身的值),原问题的解就是(d(1,1))。
- 不同的状态怎么转移呢？从格子((i,j))出发有两种决策。左走下个格子是((i+1,j))，右走下个格子是((i+1,j+1))，但是对于(i,j)来说，它只取两者中大的那个。于是状态转移方程就是：
(d(i,j)=a(i,j)+max(d(i+1,j),d(i+1,j+1)))
每个格子都有这样的选择，于是每个格子存放的都是从格子((i,j))能取到的最大值。- 如果从格子((i,j))中向下取数其中一个格子存放的不是最大值，那么(d(i,j))就一定不是最大的。这个性质称为最优子结构。(全局最优解包含局部最优解)
「动态规划的核心是状态和状态转移方程」
方法1：递归计算((dfs))各点的(d(i,j))
int solve(int i,int j) { return a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1))); }
如图(solve(1,1))调用的关系树，发现红色的部分(solve(3,2))计算调用了两次。虽然图中只有这几个点被重复，但是重复的不仅仅是单个节点，而是节点下的整棵子树。加入三角形有n层，那么调用关系树就有n层，一共有(2^n-1)个节点。「直接采用递归的方法计算状态转移方程，效率往往十分低下。原因就是相同的子问题被重复计算了很多次」
为了解决直接采用递归会超时，我们提出记忆化搜索，通常采用一个记忆数组，记录每个状态是否已经计算过。于是要初始化记忆数组(dp)
方法2 记忆化搜索+递归
int solve(int i,int j) { if(dp[i][j]>=0)//记忆数组（i,j)已经算出直接返回 { return dp[i][j]; } return dp[i][j]=a[i][j]+(i==n?0:max(solve(i+1,j),solve(i+1,j+1))); }有了这个记忆化数组，就可以保证每个节点只访问一次。
「当采用记忆化搜索时，不必事先确定各状态的计算顺序，但需要记录每个状态“是否已经计算过”」
方法3 直接递推
for(int i=1;i<=n;i++) { dp[n][i]=a[n][i]; } for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]); } }