我与动态规划-3

2020-07-20

题目 114.不同的路径

有一个机器人的位于一个 m × n 个网格左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径？

样例1

Input: n = 1, m = 3
Output: 1

Explanation: Only one path to target position.
Example 2:

样例2

Input: n = 3, m = 3

Output: 6

Explanation:
D : Down
R : Right

1) DDRR
2) DRDR
3) DRRD
4) RRDD
5) RDRD
6) RDDR

代码

class Solution:
    """
    @param m: positive integer (1 <= m <= 100)
    @param n: positive integer (1 <= n <= 100)
    @return: An integer
    """
    def uniquePaths(self, m, n):
        # write your code here
        # 存储路径数量的数组
        F=[[-1 for i in range(n)] for j in range(m)]
        
        #初始条件
        F[0][0]=0
        
        # 转移方程
        # F[n-1][m-1]=F[n-2][m-1]+F[n-1][m-2]
        
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    F[i][j]=1
                else:
                    F[i][j]=F[i-1][j]+F[i][j-1]
        print(F)
        return F[m-1][n-1]

总结

运行结果一般，但是动态规划类题，还是有经典两问：

1. 怎样打印全部结果，（打印全部结果的题该怎么做？不是用动态规划）
1. 用动态规划求最值型时，怎样打印最优的结果？*大多为初始状态+每一步的转移操作

-------------本文结束感谢您的阅读-------------