Leetcode-Question-62: Unique Paths


原文链接:
https://leetcode.com/problems/unique-paths/

题目描述:
62. Unique Paths
Difficulty: Medium

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

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 (marked ‘Finish’ in the diagram below).

robot_maze

                     Above is a 3 x 7 grid. How many possible unique paths are there?

How many possible unique paths are there?

Note: m and n will be at most 100.

解析:

法一)利用组合关系
竖走和横走加起来要走(m-1) + (n-1) 下,其中竖走要走(m-1)下。从这(m+n-2)个总的移窝中选出竖走的(m-1)个来,即为独特路径的条数。(画个图,想想看!)反之亦然。故问题转化为C(n+m-2, m-1)。
参考:https://leetcode.com/discuss/9110/my-ac-solution-using-formula

法二)动态规划
除首行和首列外,到达任一格子的路径数为:要么是竖走下来的,要么是横走过来的。有关系式:
dp[i][j] = dp[i – 1][j] + dp[i][j – 1]. 参考:
https://leetcode.com/discuss/38353/0ms-5-lines-dp-solution-in-c-with-explanations

如果对法二加以优化,那么就有(参考法二给出的链接):

 

 

Leetcode-Question-96: Unique Binary Search Trees

原文链接:
https://leetcode.com/problems/unique-binary-search-trees/

题目描述:
96. Unique Binary Search Trees
Difficulty: Medium

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

解析:动态规划法