前言
当我把手机的时间根据自己的起床时间调整以后，一切都变得奇妙起来了，我感觉这样真的蛮神圣的，先试试再说。
题目：点这里
解法
class Solution { public: int matrix[10][10]; // memset(matrix,0,sizeof(matrix)); int N; // int sum; int dfs(int u,int k){ if(k==0){ if(u==N-1){ return 1; }else{ return 0; } } int sum=0;//问题1 for(int i=0;i<N;i++){ if(matrix[u][i]){ sum += dfs(i,k-1); } } return sum; } int numWays(int n, vector<vector<int>>& relation, int k) { memset(matrix,0,sizeof(matrix)); N = n; // sum=0; //问题2 for(int i=0;i<relation.size();i++){//relation.size()不是n matrix[relation[i][0]][relation[i][1]]=1; } return dfs(0,k); } };这个题目的思路就是，首先将题目中边表示法的数组转化成邻接矩阵表示法的数组，然后利用递归深度优先搜索，寻找每一种可行的方案，最终得到总和。
反思
做题过程中出现了四个主要问题，
1.由于对邻接矩阵的不熟悉，就直接把边表示法的数组当作邻接矩阵来使用，导致出错；
2.sum作为最终存储总和的变量，声明的位置很重要，应该放在递归函数的内部，因为它每次只负责将本层的所有情况进行累加，然后将总和返回给上一层，在返回之前，上一层的sum还是0，所以每一层的sum是独立的，不同的；
3.在numWays函数内部，for循环的目的是将边表示法的数组转化成邻接矩阵的数组，所以循环的终止条件应该是基于边表示法的数组，也就是关系数，有多少个关系，就进行多少次赋值；
4.memset函数是用来给matrix数组初始化清零的，应该放在函数内部而不是类内涵数外，因为根据规则，类内部只能包含变量的声明和函数的定义，而初始化清零属于执行语句，只能放在函数内部。
记忆化搜素解法
class Solution { public: int matrix[10][10]; int N; // memo[u][k] 表示：当前在 u 点，还剩 k 步时，有多少种到达终点的方案 int memo[10][10]; int dfs(int u, int k) { // 1. 查表：如果这个状态之前算过（不等于 -1），直接返回缓存的结果 if (memo[u][k] != -1) { return memo[u][k]; } if (k == 0) { // 结果只有 1 或 0，不需要缓存（或者也可以缓存，看个人习惯） return u == N - 1 ? 1 : 0; } int sum = 0; for (int i = 0; i < N; i++) { if (matrix[u][i]) { sum += dfs(i, k - 1); } } // 2. 记录：在返回 sum 之前，先把它记在小本本上 memo[u][k] = sum; return sum; } int numWays(int n, vector<vector<int>>& relation, int k) { memset(matrix, 0, sizeof(matrix)); // 重要：把备忘录全部初始化为 -1 memset(memo, -1, sizeof(memo)); N = n; for (int i = 0; i < relation.size(); i++) { matrix[relation[i][0]][relation[i][1]] = 1; } return dfs(0, k); } };动态规划
class Solution { public: int numWays(int n, vector<vector<int>>& relation, int k) { // dp[i][j]：第 i 轮传递给编号 j 的人的方案数 // 数组大小开大一点点防止越界 vector<vector<int>> dp(k + 1, vector<int>(n, 0)); // 初始化：第 0 轮，我们在起点 0，只有 1 种方案 dp[0][0] = 1; // 开始一轮轮传递，直到第 k 轮 for (int i = 0; i < k; i++) { // 遍历所有的传递关系（边） for (auto& edge : relation) { int src = edge[0]; // 发送者 int dst = edge[1]; // 接收者 // 核心公式： // 如果第 i 轮能到达 src，那么第 i+1 轮就能从 src 到达 dst // 所以要把 src 的方案数累加给 dst dp[i + 1][dst] += dp[i][src]; } } // 最后返回：第 k 轮到达 n-1 号玩家的方案数 return dp[k][n - 1]; } };
