Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how C++ can achieve different paths. the content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Different paths to Unique Paths

A robot is located at the top-left corner of am 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)

How many possible unique paths are there?

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

Note: m and n will be at most 100.

Example 1:

Input: M = 3, n = 2

Output: 3

Explanation:

From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right-> Right-> Down

2. Right-> Down-> Right

3. Down-> Right-> Right

Example 2:

Input: M = 7, n = 3

Output: 28

This question makes it difficult for bloggers to find out the number of all different paths, because I don't seem to have encountered this kind of problem before, so I feel like I don't know how to start. After looking for a strategy on the Internet, I suddenly realized that this is very similar to the previous Climbing Stairs, which is that you can climb one or two squares at a time and ask the number of all different climbing methods that reach the top. This problem is that you can go down or to the right each time to find out the number of all the different walks in the lower right corner. Then, like the ladder climbing problem, it needs to be solved by dynamic programming Dynamic Programming, and a two-dimensional array dp can be maintained, where dp [I] [j] represents the number of different walks to the current position, and then the state transition equation can be obtained as follows: dp [I] [j] = dp [I-1] [j] + dp [I] [j]. In order to save space, one-dimensional array dp can be used to refresh one line. The code is as follows:

Solution 1:

Class Solution {public: int uniquePaths (int m, int n) {vector dp (n, 1); for (int I = 1; I

< m; ++i) { for (int j = 1; j < n; ++j) { dp[j] += dp[j - 1]; } } return dp[n - 1]; }}; 这道题其实还有另一种很数学的解法，实际相当于机器人总共走了 m + n - 2步，其中 m - 1 步向右走，n - 1 步向下走，那么总共不同的方法个数就相当于在步数里面 m - 1 和 n - 1 中较小的那个数的取法，实际上是一道组合数的问题，写出代码如下: 解法二： class Solution {public: int uniquePaths(int m, int n) { double num = 1, denom = 1; int small = m >

N? N: M; for (int I = 1; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.