概率DP【入门】 掷骰子 + hdu5001 Walk

概率dp怎么说呢，好像就是通过动态规划来算出某个状态的方案数，然后再去除以总方案数，最后的出结果。

网上找了一道入门最简单的模版题。

求投了n次之后，点数之和大于等于m的概率。

AC_code:

#include<bits/stdc++.h>
int dp[1005][1005];
using namespace std;

int main(){
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	int n, m;
	cin>>n>>m;
	dp[0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= 6*i; j++){
			for(int k = 1; k <= 6; k++){
				dp[i+1][j+k] += dp[i][j];//前一次的投的方案数加上这一次投的数字   的方案数 
			}
		}
	}
	int ans = 0;
	for(int i = m; i <= 6*n; i++){
		ans += dp[n][i];
	}
	int sum = 1;
	for(int i = 0; i < n; i++){
		sum *= 6;
	}
	int temp = __gcd(ans, sum);
	cout<<ans/temp<<"/"<<sum/temp<<endl;
	return 0;
}

hdu5001 walk

给你n个点，m条边，你可以从任意一个点出发，一共走s步

请问不经过每一个点的概率为多少？

思路： 假设我们要忽略的点为v，  动态规划算出每一步才到达v的概率为多少，对所有步数到达v点的概率加起来，最后答案为1减去到达v点的概率，有一个点要记住，就是当前步已经走到了v，那么接下来的就不用考虑了。

AC_code:

#include<bits/stdc++.h>
#define ll long long
#define maxn 65
#define maxm 10005
using namespace std;
double dp[maxm][maxn];
double ans[maxn];
vector<int> edge[maxn];
int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	int n, m, t, s;
	cin>>t;
	while(t--) {
		for(int i = 0; i <= maxn; i++){
			edge[i].clear();
		}
		memset(ans, 0, sizeof(ans));
		cin>>n>>m>>s;
		int a, b;
		for(int i = 0; i < m; i++) {
			cin>>a>>b;
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
		for(int v = 1; v <= n; v++) { //n 个 点不同的概率
			memset(dp, 0, sizeof(dp));
			for(int i = 1; i <= n; i++) { //初始化每个起点的概率
				dp[0][i] = 1.0/n;
			}
			ans[v] += dp[0][v];
			for(int j = 0; j < s; j++) {
				for(int i = 1; i <= n; i++) {
					if(i == v) { //已经到达这个点的时候就不必继续动态规划了
						continue;
					}
					for(int ne = 0; ne < edge[i].size(); ne++) {
						if(i == edge[i][ne]) {
							continue;
						}
						dp[j+1][edge[i][ne]] += dp[j][i] * (1.0/edge[i].size());// 每个点
					}
				}
				ans[v] += dp[j+1][v];
			}
		}
		for(int i = 1; i <= n; i++) {
			printf("%.10lf\n",1.0 - ans[i]);
		}
	}
	return 0;
}