原题
LCP 07.传递信息
题解
方法一 动态规划
动态规划说明某一种状态一定与前一种或者前几种状态有关。我们不妨设立一个二维数组ans，其中ans[j][i]表示的是，从0开始，通过j+1步到达i的方式种数。
在一开始的时候，我们需要初始化第0行，也就是从0位置开始，第一步就能到达的地方；之后再根据从1到k-1，每一种步数用一个循环周期，在每个循环周期内遍历relations，ans[j][i]等于所有ans[j-1][k]的和，其中k表示的是relation中第二位置是i的第一个位置的值。
本思路java代码示例：
/* @v7fgg 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 内存消耗：37.2 MB, 在所有 Java 提交中击败了100.00%的用户 2020年7月19日 15:38 */
class Solution {public int numWays(int n, int[][] relation, int k) {//ans[j][i]表示从0开始，通过j+1步到达i的方式种数int ans[][]=new int[k][n];//ans[0][?]也就是第一步到达某位置的种数for(int i=0;i<relation.length;i++){if(relation[i][0]==0){ans[0][relation[i][1]]++;}}//ans[j][?]跟ans[j][??]有关，其中??表示能到达?的所有点for(int j=1;j<k;j++){for(int i=0;i<relation.length;i++){ans[j][relation[i][1]]+=ans[j-1][relation[i][0]];}}return ans[k-1][n-1];}
}