夕拾算法进阶篇：12)出栈序列统计(动态规划DP)

5

该题虽然是栈的范畴，但是也可以使用动态规划来做。这个题DP的解法可以借用2点之间路径的数目来求解，先看下面的图片：

之前的题目要求：只能向下或右走，从左上角到右下角公有多少条路径？

其解法如下：

如果要求A1->D4的路径数目，可先求D3->D4和C4->D4的路径数目，而求D3的路径数目，可以求D2->D3和B3-C3的数目。这是一个重叠子问题，可以使用DP来解决，很明显其状态转移方程(边界0~n)：

dp[i][j]=dp[i-1][j]+dp[i][j-1]

这里可以把向下类比入栈，向右类比出栈。通常出栈之前必须保证栈内有元素，所以出栈次数<=入栈次数。因为从起点(左上角) 向右出栈是非法的，所以 整个图只有下三角是我们考虑的区域，也可以把上三角的点坐标值视为0。

初始化起点A1的值为1，由于B1只有上邻而没有左邻节点，所有B1的值也为1，事实上第一列的值皆为1，因此求栈的出栈序列的数目，即求N*N的矩阵对应下三角的路径数目。(PS:矩阵的N*N得用数组a[N+1][N+1]保存)

#include<iostream>using namespace std; const int M=17;int dp[M][M];  int main(){	int n,i,j;	cin>>n;	for(i=0;i<=n;i++){   		dp[i][0]=1;//第一列置1     }   	for(i=1;i<=n;i++){   		for(j=1;j<=n;j++){   			if(i>=j){   				dp[i][j]=dp[i-1][j]+dp[i][j-1];			}		}		}	cout<<dp[n][n]<<endl; }
题目来源：http://www.codeup.cn/PRoblem.php?cid=100000608&pid=4