对问题的解空间搜索(暴力)解空间，即所有路径。
Dfs(i, j) {
if (i > n) {
ans >?=
cmax;
return ;
}
cmax += Triangle[i][j];
Dfs(i+1, j);
Dfs(i+1, j+1);
cmax -= Triangle[i][j];
}
分析：对n层的数塔，路径数为2^n-1。
问题的子结构：
假设一个最优解的路径所到达的最底层位置是k，即最后选Triangle[n][k]。能到达Triangle[n][k]的只有Triangle[n-1][k-1]和Triangle[n-1][k]。再假设此最优路径经过Triangle[n-1][k]。 问题：从Triangle[1][1]到达Triangle[n-1][k]的路径是不是最优的？
最优子结构：
用cut&paste，可证得此路径必然是最优的。这是DP最基本的原理。现对到达Triangle[i][j]的路径，设为状态ans[i][j]。由上分析可得到一个递推关系式:ans[i][j]
= max{ans[i-1][j],
ans[i-1][j-1]} + Triangle[i][j]此式即状态转移方程，加号前面项即所做出的决策。初始化(边界)：置ans表为0。
重叠子问题：
对状态ans[i][j]和ans[i][j+1]，这两个状态都可能由ans[i-1][j]转移而来。那么这样，自顶向下计算、转移，每次会重复计算子问题多次。所以应该用自底向上的计算方式，对此题，即每次先计算第i-1层的最优值。
典型问题三：最长上升子序列
问题描述：
给出一个序列，求它最长的上升子序列．例如，序列{1,7,3,5,9,4,8},其中{1,7}, {3,4,8},{1,3,5,8},都是它的上升子序列，而{1,3,5,8}是它的最长的上升子序列．
提示：状态选择：best[i]代表以序列中第i个数为最后一个数时，最长上升子序列的长度．状态转移方程：best[i]=max{1,max{best[j]+1,num[j]<num[i]&&j<i}}所有best[]值里最大的那个就是最优值．初始条件：best[i]=1,1<=i<=n．
核心代码：
for(i=1;i<=n;i++) best[i]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(num[j]<num[i]&&best[j]+1>best[i])
best[i]=best[j]+1;
}
}
max=0;
for(i=1;i<=n;i++)
if(best[i]>max) max=best[i];
典型问题四：最长公共子串
问题叙述：
给出两个字符串，求它们最长的公共子字符串．比如，两个字符串abcfbc和abfcab，其中abb,abcb,abfc都是它们的公共子串，而abcb,abfc是它们的最长公共子串
提示：状态选择：dp[i][j]代表第一个字符串前i个字符组成的字符串与第二个字符串前j个字符组成的字符串的最长公共子串的长度．状态转移方程：如果str1[i]==str2[j],dp[i][j]=dp[i-1]
[j-1]+1;否则dp[i][j]=max{
dp[i-1][j],dp[i]
[j-1]}.初始条件：dp[0][j]=0,0<=j<=len2;dp[i][0]=0,0<=i<=len1.
for(i=0;i<=len1;i++) dp[i][0]=0;
for(j=0;j<=len2;j++) dp[0][j]=0;
for(i=1;i<=len1;i++)
for(j=1;j<=len2;j++)
{
if(str1[i]==str2[j])
dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
}
学无止境，稍稍分享了一下心得~~
