一个神奇的递推公式--转自2108

zy兄发现了一个神奇的递推公式,

某些递推的题目可以看作, 一个个上三角阵, 而问题的解为(1,1) 至 (n,n) 的路径个数, 废话不多说, 上题上代码

以下转自http://www.cnblogs.com/--ZHIYUAN/p/5971367.html

小兔的棋盘

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9447 Accepted Submission(s): 4879

Problem Description

小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!

Input

每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。

Output

对于每个输入数据输出路径数，具体格式看Sample。

Sample Input

1

3

12

-1

Sample Output

1 1 2

2 3 10

3 12 416024

Author

Rabbit

Source

RPG专场练习赛

代码：

 1 /*
 2 原来不经过对角线是路径不穿过对角线的意思啊。递推打表，可以把棋盘下半部分遮住只看上半部分级列数大于等于行数的部分，这样每一个点(x,y)可以由(x-1,y),(x,y-1)推得
 3 最后得到一半棋盘的结果再乘2。
 4 */
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<cstring>
 8 using namespace std;
 9 long long a[40][40];
10 void init()
11 {
12     memset(a,0,sizeof(a));
13     for(int i=1;i<37;i++)
14     a[i][0]=1;
15     for(int i=1;i<37;i++)
16     {
17         for(int j=1;j<=i;j++)
18         {
19             a[i][j]=a[i-1][j]+a[i][j-1];
20         }
21     }
22 }
23 int main()
24 {
25     int t=0,n;
26     init();
27     while(scanf("%d",&n)&&n!=-1)
28     {
29         t++;
30         printf("%d %d %lld
",t,n,a[n][n]*2);
31     }
32     return 0;
33 }

下沙的沙子有几粒？

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3935 Accepted Submission(s): 2074

Problem Description

2005年11月份，我们学校参加了ACM/ICPC 亚洲赛区成都站的比赛，在这里，我们获得了历史性的突破，尽管只是一枚铜牌，但获奖那一刻的激动，也许将永远铭刻在我们几个人的心头。借此机会,特向去年为参加ACM亚洲赛而艰苦集训了近半年的各位老队员表示感谢。
实际上，除了获奖以外，在这次比赛期间还有一件事也让我们记忆深刻。那是比赛当天等待入场的时候，听到某个学校的一个队员在说：“有个学校的英文名很有意思，叫什么Hangzhou Dianzi University”. 哈哈，看来我们学校的英文名起的非常好，非常吸引人呀。
不过，事情的发展谁也没有料到，随着杭电英文校名的这一次曝光，影响越来越大，很多人开始对杭电英文校名进行研究，不久以后甚至还成立了一个专门的研究机构，叫做“HDU 校名研究会”。并不断有报道说-相-当-多的知名科学家改行，专门对该问题进行研究，学术界称之为“杭电现象”。很多人在国际知名期刊上发表了研究论文，这其中，尤以中国超级女科学家宇春小姐写的一篇研究报告最为著名，报告发表在science上，标题是“杭电为什么这样红？” 文中研究发现：Hangzhou Dianzi University这个校名具有深刻的哲学思想和内涵，她同时提出了一个大胆的猜想：“假定一个字符串由m个H和n个D组成，从左到右扫描该串，如果字符H的累计数总是不小于字符D的累计数,那么，满足条件的字符串总数就恰好和下沙的沙粒一样多。”
这就是当今著名的“宇春猜想”！
虽然还没能从数学上证明这个猜想的正确性，但据说美国方面在小布什的亲自干预下，已经用超级计算机验证了在（1<=n<=m<=1000000000000）时都是正确的。my god! 这是一个多么伟大的猜想！虽然我们以前总说，21世纪是属于中国的，可还是没想这一天来的这么早，自豪ing... + 感动ing...
感动和自豪之余，问题也来了，如果已知m和n的值，请计算下沙的沙粒到底有多少。

Ps:
1. 中国有关方面正在积极行动，着手为宇春小姐申报诺贝尔奖。
2、“宇春猜想”中提到的H和D组成的字符串现在被学术界成为“杭电串串”（“杭电串串”前不久被一个卖羊肉串的注册了商标，现在我校正在积极联系买断，据说卖方的底价是1000万欧元，绝不打折，看来希望不大，sigh...）

Input

输入数据包含多个测试实例，每个占一行，由两个整数m和n组成，m和 n 分别表示字符串中H和D的个数。由于我们目前所使用的微机和老美的超级计算机没法比，所以题目给定的数据范围是（1<=n<=m<=20）。

Output

对于每个测试实例，请输出下沙的沙粒到底有多少，计算规则请参考“宇春猜想”，每个实例的输出占一行。

Sample Input

1 1
3 1

Sample Output

1
3

Author

lcy

Source

HDU 2006-4 Programming Contest

代码：

 1 //见鬼了，这两道题的递推公式竟然一样。本来这道题想用dfs来搜但超时，然后发现数据结果竟和上一道题一样。可以这样想，
 2 //设行H用列代表，D用行代表，列数要永远大于行数，这样又转换成了一个上三角的半个方格阵，求从求从起点到目标点的路径数。
 3 #include<iostream>
 4 #include<cstdio>
 5 using namespace std;
 6 int n,m;
 7 long long a[21][21];
 8 void init()
 9 {
10     for(int i=1;i<=20;i++)
11     a[i][0]=1;
12     for(int i=1;i<=20;i++)
13     {
14         for(int j=1;j<=i;j++)
15         {
16             a[i][j]=a[i-1][j]+a[i][j-1];
17         }
18     }
19 }
20 int main()
21 {
22     init();
23     while(scanf("%d%d",&n,&m)!=EOF)
24     {
25         printf("%lld
",a[n][m]);
26     }
27     return 0;
28 }

How Many Trees?

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3754 Accepted Submission(s): 2108

Problem Description

A binary search tree is a binary tree with root k such that any node v reachable from its left has label (v) <label (k) and any node w reachable from its right has label (w) > label (k). It is a search structure which can find a node with label x in O(n log n) average time, where n is the size of the tree (number of vertices).

Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?

Input

The input will contain a number 1 <= i <= 100 per line representing the number of elements of the set.

Output

You have to print a line in the output for each entry with the answer to the previous question.

Sample Input

1
2
3

Sample Output

1
2
5

Source

UVA

代码：

 1 package luzhiyuan;
 2 import java.util.Scanner;
 3 import java.math.BigInteger;
 4 public class java1 {
 5     public static void main(String[] args){
 6         BigInteger [][]a=new BigInteger[102][102];
 7         BigInteger sta=BigInteger.valueOf(1);     //把其他形式的数化为大整数
 8         BigInteger zeo=BigInteger.valueOf(0);
 9         for(int i=0;i<=100;i++)
10             for(int j=0;j<=100;j++)
11                 a[i][j]=zeo;        //如果想让后面的加法函数可用一定要给大整数赋初值
12         for(int i=1;i<=100;i++)
13             a[i][0]=sta;
14         for(int i=1;i<=100;i++)
15             for(int j=1;j<=i;j++){
16                 a[i][j]=a[i][j].add(a[i-1][j]);
17                 a[i][j]=a[i][j].add(a[i][j-1]);
18             }
19         Scanner cin=new Scanner(System.in);
20         while(cin.hasNext()){
21             int n=cin.nextInt();
22             System.out.println(a[n][n]);
23         }
24     }
25 }

还有一道题脑洞大开地运用了此递推方法:

1001: Buy the Ticket

Problem Description

The "Harry Potter and the Goblet of Fire" will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?

Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).

Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person.

Note: initially the ticket-office has no money.

The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.

Input

The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.

Output

For each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.

Sample Input

3 0

3 1

3 3

0 0

Sample Output

Test #1:

Test #2:

Test #3:

180

Source

HUANG, Ninghai

以为50元的数目要一直大于100元的数目, 这样就和下沙的沙子那道题一模一样了, 又见春哥...(逃....