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