DP真题

骨骼清奇:
LC 62
LC 337 House Robber III
LC 486 Predict the Winner
LC 312 Burst Balloons
Onsite: 考察dp的，类似与有多少条路径，从起点到终点，在一个二维grid上，leetcode有相似的题，然后如果遇到障碍或者必须经过某些位置的话咋办
[Uber] LC 91 Decode Ways
[Uber] 911 Online Election
[Uber] LC 72 Edit Distance

LC六二
A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

著名变种：给定一个矩形的长宽，用多少种方法可以从左上角走到右上角 （每一步，只能向正右、右上 或 右下走）：整个矩形遍历做DP即可，不需要想复杂。
-follow up：如果给矩形里的三个点，要求解决上述问题的同时，遍历这三个点 （切割矩形，一个一个地做DP，然后相加）
-follow up：如何判断这三个点一个是合理的，即存在遍历这三个点的路经
-follow up：如果给你一个H，要求你的路径必须向下越过H这个界。

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if not m or not n: return 0
        dp = [[1]*n for _ in range(m)]
        for i in  range(1,m):
             for j in range(1,n):
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]