# 4.5算法之动态规划 191:钉子和小球 概率

#### 题目

http://noi.openjudge.cn/ch0405/191/

#### 思路

n = 2 时，第 0 层为钉子的上一层，初始小球

– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

#### 源码

``````//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<long long>> dp;
vector<vector<char>> cnt;
long long gcd(long long x,long long y){
return y?gcd(y,x%y):x;
}
int main(){
long long n,m;
cin >> n >> m;
cnt.resize(n+1,vector<char>(n+1));
dp.resize(n+1,vector<long long>(n+1,0));
for(long long i = 1;i <= n; ++i){
for(long long j = 1;j <= i; ++j){
char c;
cin >> c;
cnt[i][j]=c;
}
}
//
dp[0][0] = pow(2,n);
for(long long i = 1;i <= n;++i){
for(long long j = 0;j <= i; ++j){
//处理左右边界
if(j == 0){
if(cnt[i][j+1]=='*'){
dp[i][j]=dp[i-1][j]/2;
}else{
dp[i][j]=0;
}
}else if(j == i){
if(cnt[i][j]=='*'){
dp[i][j]=dp[i-1][j-1]/2;
}else{
dp[i][j]=0;
}
}else{
if(cnt[i-1][j]=='.'){
dp[i][j]+=dp[i-2][j-1];
}
if(cnt[i][j]=='*'){
dp[i][j]+=dp[i-1][j-1]/2;
}
if(cnt[i][j+1]=='*'){
dp[i][j]+=dp[i-1][j]/2;
}
}
}
}

long long a = dp[n][m],b = dp[0][0];
long long gc=gcd(b,a);
a/=gc;
b/=gc;
cout << a<<"/"<<b;

return 0;
}

``````