本文主要是介绍poj 1189 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我觉得有一种情况 网上代码没考虑 但是可以AC poj数据很弱：
5 3
*
* *
* * *
* * * *
. . . . .
这样算出来每个洞里的概率都为0 应该是错的 因为有个方程 dp[i+2][j+1]+=dp[i][j]; 会忽略已经掉到洞里了。
#include<cstdio>
#include<cstring>
long long gcd(long long a,long long b)
{return b==0?a:gcd(b,a%b);
}
long long dp[55][55];
int main()
{int n,m;char str[60][60],ch;scanf("%d%d",&n,&m);getchar(); for(int i=1;i<=n;i++){int tot=1;while((ch=getchar())!='\n'){if(ch=='*'||ch=='.'){str[i][tot]=ch;tot++;}}}dp[1][1]=1LL<<n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(str[i][j]=='*'){dp[i+1][j]+=dp[i][j]>>1;dp[i+1][j+1]+=dp[i][j]>>1;}else{if(i==n){dp[i+1][j+1]+=dp[i][j]>>1;dp[i+1][j]+=dp[i][j]>>1;}elsedp[i+2][j+1]+=dp[i][j];}}}long long int res=gcd(1LL<<n,dp[n+1][m+1]);printf("%lld/%lld\n",dp[n+1][m+1]/res,(1LL<<n)/res);return 0;
}这篇关于poj 1189 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
