题目链接：http://poj.org/problem?id=1189
dp
可以知道一共有2^n条路径，则设顶点有2^n个球，若当前为'*'则向左右的球各有一半；若为'.'，则球全部掉入正下方。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 char ma[55][55]; 9 long long f[55][55]; 10 long long gcd(long long a,long long b) 11 { 12 if(a==0) return b; 13 return gcd(b%a,a); 14 } 15 int main() 16 { 17 long long n,m; 18 scanf("%lld%lld",&n,&m); 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=i;j++) cin>>ma[i][j]; 21 long long t=1; 22 t=1LL<<n; 23 f[1][1]=t; 24 for(int i=2;i<=n+1;i++) 25 { 26 for(int j=1;j<=i;j++) 27 { 28 if(ma[i-1][j]=='*'){f[i][j]+=f[i-1][j]/2;f[i][j+1]+=f[i-1][j]/2;} 29 else f[i+1][j+1]+=f[i-1][j]; 30 } 31 } 32 long long c=gcd(f[n+1][m+1],t); 33 cout<<(f[n+1][m+1])/c<<'/'<<t/c; 34 system("pause"); 35 }