【题目练习】不同路径

题目解题运行结果解题思考第一步一共要走多少步从左上角到右下角需要向下走m-1 次 需要向右走n-1 次总步数 (m−1)(n−1)mn−2步问题等价于在这总共 mn−2 步里选 m−1 步向下剩下自动向右就是组合数样例代入m3,n7 mn−28,m−12 最后为28二、分析移动规律从起点(0,0)到终点(2,6)想要到达终点必须向下走几步一共 3 行从第 0 行到第 2 行向下走 m-1 3-1 2 次必须向右走几步一共 7 列从第 0 列到第 6 列向右走 n-1 7-1 6 次固定结论不管走哪一条合法路径都一定是向下 2 次 向右 6 次总共 8 步区别只在于这 8 步里面什么时候向下、什么时候向右。问题转化在 8 个位置里选 2 个位置安排 “向下”剩下自动是向右。​三、DP 状态定义定义dp[i][j] 走到坐标 (i,j) 这个格子一共有多少条不同路径。我们的目标求 dp[2][6]终点位置边界情况初始化1、 第一行 i0(0,0)、(0,1)、(0,2)...(0,6)第一行的格子机器人不可能从上面来上面没有格子只能一直向右走才能到达。第一行所有格子路径数都是 1 dp[0][j] 12、第一列 j0(0,0)、(1,0)、(2,0)第一列的格子机器人不可能从左边来左边没有格子只能一直向下走才能到达。第一列所有格子路径数都是 1 dp[i][0] 1四、推导状态转移方程想一想怎么走到 (i,j)因为机器人只能向右、向下走反过来理解能走到(i,j)的来源只有两个1、从它正上方格子 (i-1,j) 向下走一步过来2、从它左边格子 (i,j-1) 向右走一步过来所以dp[i][j]dp[i−1][j]dp[i][j−1]到达当前格子的路径总数 上方格子路径数 左边格子路径数填表顺序一行一行从左往右填i 从 1 开始j 从 1 开始跳过已经初始化的第一行、第一列五、翻译成 C 语言代码