力扣 1377 https://leetcode.cn/problems/frog-position-after-t-seconds/

这道题目用dp去做,构建邻接矩阵，做的时候需要注意题目条件，如果青蛙跳不动了，这个概率就保持不变了

一般跳青蛙，很容易想到dp

核心代码如下

public double frogPosition(i

public double frogPosition(int n, int[][] edges, int t, int target) {

// 用邻接矩阵表示
int[][] graph = new int[n+1][n+1];

for (int i = 0; i < edges.length; i++) {  
    int\[\] edge = edges\[i\];

    int start=edge\[0\];  
    int end=edge\[1\];  
//    无向图  
    graph\[start\]\[end\]=1;  
    graph\[end\]\[start\]=1;

}  
int\[\] isVisit = new int\[n+1\];  
//1.dp\[i\]\[j\] 表示i顶点 j秒时候的概率  
double\[\]\[\] dp = new double\[n+1\]\[t+1\];

// 2.递推见循环

// 3.初始化1号点
dp[1][0]=1;
isVisit[1]=1;
for (int time = 1; time <= t; time++) {

//    拿出当前time--的值 从它们出发 ，然后计算能够到达的点

    for (int i = 0; i < dp.length; i++) {

        if (dp\[i\]\[time-1\]!=0){  
        //    这个地方可以往下面走

        //    顶点是i

        //    找顶点i的临界节点  
          List<Integer> neithbor =getNeighbor(graph,i,isVisit);

        //  这些节点 新加概率  
            for (int j = 0; j < neithbor.size(); j++) {

                dp\[neithbor.get(j)\]\[time\]+=dp\[i\]\[time-1\]/neithbor.size();  
                isVisit\[neithbor.get(j)\]=1;

            }

        //    如果neithbor.size是0的话，说明谁也到不了，以后这个点的概率就固定死了  
            if (neithbor.isEmpty()){  
                for (int j = time; j <= t; j++) {  
                    dp\[i\]\[j\]=dp\[i\]\[time-1\];  
                }  
            }

        }

    }

}

// for (int i = dp\[target\].length-1; i >=0; i--) {  
//     if (dp\[target\]\[t\]!=0){  
//         return dp\[target\]\[t\];  
//     }  
//     t--;  
// }

return dp\[target\]\[t\];

}

private List getNeighbor(int[][] graph, int start, int[] isVisit) {

ArrayList<Integer> list = new ArrayList<>();  
int\[\] neithbor = graph\[start\];

for (int i = 0; i < neithbor.length; i++) {  
    if (neithbor\[i\]==1){  
        if (isVisit\[i\]==0){  
            list.add(i);  
        }  
    }  
}  
return list;  

}

更好的

官方用了dfs去做

dfs思路是判断这个节点有多少个叶子节点

一层层递归进去，知道找到了target，再往外返回的时候，计算ans/节点个数

起始只要算节点有多少个就行了，要经过多少次边才会到达这个节点

比如说题目给的图片 4递归回去2 有2个节点，2递归回去1有3个节点 ，那么4的概率就是1/(2*3)

民间有个很好的想法

该怎么避免精度丢失，让精度丢失的越少越好

做法 既然答案是由若干分子为 的分数相乘得到，那么干脆只把分母相乘，最后再计算一下倒数，就可以避免因浮点乘法导致的精度丢失了。另外，整数的计算效率通常比浮点数的高。