一个机器人站立在 m×n 方格的左上角(下图中标记为"Start"的位置).
这个机器人只能向右或向下移动.机器人正在试着移动到方格的右下角(下图中标记为"Finish"的位置).
共有多少条不同的路径可以移动?
上图是 7×3 的方格,共有多少种可能的路径?
从左上角开始,共有 3 条路径可以到达右下角:
这个题也很有意思,猛的一看很简单,就是一个数理统计问题嘛.
对于这个题,我们当然可以用数学方法去解,这也是大多数人第一次遇到这个问题的想法.同时这个题我们也可以用动态规划来解.
思考一下便可知,从起点到达某一个位置的路径数量,等于 从起点到达其左边的位置的路径数量 与 从起点到达其上边的位置的路径数量 之和.而当这个位置在第一行或第一列时,路径数量为确定的 1,这样我们就可以递归把任意位置的路径数量算出来.