蘑菇阵（动态规划）

题目：
现在有两个好友甲和B，住在一片长有蘑菇的由n * m个个方格组成的草地，A在（1,1），B在（N，M）。现在甲想要拜访B，由于她只想去乙的家，所以每次她只会走（I，J + 1）或第（i + 1，j）的这样的路线，在草地上有ķ个蘑菇种在格子里（多个蘑菇可能在同一方格），问：甲如果每一步随机选择的话（若她在边界上，则只有一种选择），那么她不碰到蘑菇走到乙的家的概率是多少？
链接：https://www.nowcoder.com/questionTerminal/ed9bc679ea1248f9a3d86d0a55c0be10

我对这道题的思路是：

用两个二维数组分别来存放蘑菇阵和每一步的几率，这两个数字是一一对应的。

将第一步视作概率为一

在对应的格子中记录从每个格子开始走的几率，判断依据是：如果这个格子是边界，那么只有一条路，所以概率为1，如果这个格子里有蘑菇，那么概率一定是0，否则这个从这个格子出发的概率为0.5

将之前的概率与现在的概率相乘，得到并记录从这个格子出发的概率

#include <iostream> #include <vector> #include <iomanip>using namespace std;int main() {int n,m,k;while(cin >> n >> m >> k){//由于这里的坐标是从（1，1）开始的，所以将数组的大小定义为n+1*m+1vector<vector<int> > Lawn((n+1),vector<int>(m+1));vector<vector<double> > Ret((n+1),vector<double>(m+1));//将Lwan中的种上蘑菇for(size_t i = 0; i < k; ++i){int x,y;cin >> x >> y;Lawn[x][y] = 1;}//将开始位置初始化为1.0Ret[1][1] = 1.0;//开始一层一层的看Lawn中的路线中的蘑菇for(size_t i = 1; i < n+1; ++i){for(size_t j = 1; j < m+1; ++j){//如果着块草地有蘑菇，无论怎么走都是0if(1 == Lawn[i][j]){Ret[i][j] = 0;continue;}if(!(1 == i && 1 == j)){//如果是边界，那几率就是1，因为只有一条路Ret[i][j] = Ret[i-1][j]*(j == m ? 1.0:0.5) + Ret[i][j-1]*(i == n ? 1.0:0.5);}}}cout << fixed << setprecision(2) << Ret[n][m] << endl;}return 0; }

总结

以上是生活随笔为你收集整理的蘑菇阵（动态规划）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。