題目鏈接：http://ac.jobdu.com/problem.php?pid=1547

題目描述：

給定一個初始為空的棧，和n個操作組成的操作序列，每個操作只可能是出棧或者入棧。
要求在操作序列的執行過程中不會出現非法的操作，即不會在空棧時執行出棧操作，同時保證當操作序列完成后，棧恰好為一個空棧。
求符合條件的操作序列種類。
例如，4個操作組成的操作序列符合條件的如下：
入棧，出棧，入棧，出棧
入棧，入棧，出棧，出棧
共2種。

輸入：

輸入包含多組測試用例，每組測試用例僅包含一個整數n(1<=n<=1000)。

輸出：

輸出僅一個整數，表示符合條件的序列總數，為了防止總數過多超出int的范圍，結果對1000000007取模(mod 1000000007)。

樣例輸入：

2 4 10

樣例輸出：

1 2 42

解答思路 ：

dp(i,j)表示 i個操作之后，棧里面的數據個數

狀態轉移?dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])

代碼：

#include <bits/stdc++.h> using namespace std;int dp[1001][1001];int main(){dp[2][0] = 1;dp[2][1] = 0;dp[2][2] = 1; for (int i = 3 ; i<1001 ; i++){for (int j = 1 ; j < i ; j++){dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%1000000007;}dp[i][0] = dp[i-1][1];dp[i][i] = dp[i-1][i-1]; }int n ;while (cin>>n){cout<<dp[n][0]<<endl;}return 0; }

下面是問題1547第1583430號解答的執行結果：一共5個案例，通過5個

測試案例 結果??? 內存 耗時 得分/滿分

1	Accepted	5432?kb	10?ms	20/20
2	Accepted	5432?kb	10?ms	20/20
3	Accepted	5432?kb	10?ms	20/20
4	Accepted	5432?kb	10?ms	20/20
5	Accepted	5432?kb	10?ms	20/20

總結

以上是生活随笔為你收集整理的九度OJ 1547 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。