5

該題雖然是棧的范疇，但是也可以使用動態(tài)規(guī)劃來做。這個題DP的解法可以借用2點之間路徑的數(shù)目來求解，先看下面的圖片：

之前的題目要求：只能向下或右走，從左上角到右下角公有多少條路徑？

其解法如下：

如果要求A1->D4的路徑數(shù)目，可先求D3->D4和C4->D4的路徑數(shù)目，而求D3的路徑數(shù)目，可以求D2->D3和B3-C3的數(shù)目。這是一個重疊子問題，可以使用DP來解決，很明顯其狀態(tài)轉(zhuǎn)移方程(邊界0~n)：

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

這里可以把向下類比入棧，向右類比出棧。通常出棧之前必須保證棧內(nèi)有元素，所以出棧次數(shù)<=入棧次數(shù)。因為從起點(左上角) 向右出棧是非法的，所以 整個圖只有下三角是我們考慮的區(qū)域，也可以把上三角的點坐標(biāo)值視為0。

初始化起點A1的值為1，由于B1只有上鄰而沒有左鄰節(jié)點，所有B1的值也為1，事實上第一列的值皆為1，因此求棧的出棧序列的數(shù)目，即求N*N的矩陣對應(yīng)下三角的路徑數(shù)目。(PS:矩陣的N*N得用數(shù)組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