Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

O path

Problem description

A robot is in the upper left corner (starting point) of an M by N map. The robot can move down or to the right each time. The robot should arrive at the bottom right corner of the map. How many different paths can you take to get from the beginning to the end?

Example:

Input: m = 3, n = 2 Output: 3 Description: There are three paths to the lower right corner starting from the upper left corner.

  1. Right -> down -> down
  2. Down -> down -> to the right
  3. Down -> right -> down

To analyze problems

According to the meaning of the question, since the robot can only choose to go down or right, for matrix[M-1] [N-1] at the lower right corner, it can go down from the top of the position, that is, from Matix [M-2] [N-1], or go right from the left of the position. That is, matrix[m-1] [N-2] to the right.

We define an m*n matrix dp, where dp[I] [j] represents the number of schemes from the starting point to row I and column J. According to the previous analysis, we can clearly know that dp[I] [j] = DP [i-1] [j] + DP [I] [J-1]. Therefore, we can use the idea of dynamic programming to solve the problem, and its state transition equation is DP [I] [j] = DP [i-1] [j] + DP [I] [J-1].

For the elements in the first row, there is only one way to go, which is to go right from the left position; For the first column, there’s only one way to go, only from the top down.

Let’s take a look at how the code works.

class Solution: def uniquePaths(self,m ,n): Dp = [1 for _ in range(n)] for _ in range(m)] dp for I in range(1,m): for j in range(1,n): # according to the equation of state, filling matrix dp [I] [j] = dp [j] + [I - 1] dp [I] [1] return dp [m - 1) [n - 1)Copy the code

The time complexity and space complexity of the algorithm are O(m*n).

To optimize the

We know that to get from the top left corner to the bottom right corner, it takes m minus 1+n minus 1 steps, including m minus 1 steps down and n minus 1 steps to the right. Since we can only go down or right, so when we choose m-1 of the m+n-2 steps to go down, the remaining N-1 steps can only go right (or choose n-1 of the steps to go right, the remaining M-1 steps can only go down), and the total number of options is EITHER C(m+n-2, m-1) or C(m+n-2, n-1). Yes, This is permutation and combination in mathematics.

**Tips: C(n,m)=n * (n-1) … (n-m+1) / (m * (m-1) * (m-2) … * * * 1)

Class Solution: def uniquePaths(self,m,n): # class Solution: def uniquePaths(self,m,n): #C(n,m)= n * (n-1) *... * (n-m+1) / (m * (m-1) * (m-2) ... Num = 1.0 for I in range(1,k+1) = 1 for I in range(1,k+1) num=num * (count - k + i ) / i return int(num)Copy the code