动态规划，递推（杆子的排列，uva 1638）

杆子的排列，uva 1638）"/>

动态规划，递推（杆子的排列，uva 1638）

一开始用排列组合做，写完了后才发现是错的，虽然能过样例。

以后一定要先确定解法正确，再编写代码。否则简直浪费时间。

最后看了书是用动态规划。动态规划的特点就是有状态和决策。我们可以通过在某个状态上的某个位子放一个杆子来转移到下一个状态。

紫书上说杆子的具体高度不影响结果，我的理解就是你只用知道所有杆子的长度不同，长和短是相对而言的，题目要求你出所有不同长短关系的序列。我们发现通过放一个更短的杆子来实现状态转移会十分的方便。想通了这点，转移方程就很容易找到了。

三维的状态是不能少的，首先杆子的个数必须要作为一维，因为转移和求解都需要他，这是核心。但这不够，信息量太少，只有再分别加上l和r两维，才能提供足够多的信息，事实上，你也只有l和r能作为维了。

发现有些数学题的递推很像或根本就是动态规划。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll dp[25][25][25];void init()
{dp[1][1][1]=1;for(ll i=2;i<=20;i++)for(ll j=1;j<=i;j++)for(ll k=1;k<=i;k++)if(j+k>=3&&j+k<=i+1)dp[i][j][k]=dp[i-1][j-1][k]+dp[i-1][j][k-1]+dp[i-1][j][k]*(i-2);
}int main()
{init();ll T;scanf("%lld",&T);while(T--){ll n,l,r;scanf("%lld %lld %lld",&n,&l,&r);printf("%lld\n",dp[n][l][r]);}return 0;
}