对于每一个同学接到球的来源可以是前一个同学,也可以是后一个同学,且还需要考虑传球次数,因此可以尝试设计状态:dp[i][j] 表示从 1 号开始传球,总共传递了 j 次,传递到 i 号的种类次数。例如 dp[1][0] 表示从 1 号开始传球传 0 次,到达 1 号。显而易见的 dp[1][0] = 1 。根据传球的来源不同,可以做如下划分:
从小编号传来:dp[i-1][j-1]
从大编号传来:dp[i+1][j-1]
因此 dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1];