Shulou(Shulou.com)06/02 Report--

This article mainly introduces the relevant knowledge of "Java dynamic programming and combinatorial number case analysis". The editor shows you the operation process through the actual case. The operation method is simple, fast and practical. I hope this article "Java dynamic programming and combinatorial number case analysis" can help you solve the problem.

Start with the title.

The original title is:

A robot is located in the upper-left corner of a m x n grid (the starting point is marked "Start" in the following figure).

The robot can only move down or to the right one step at a time. The robot attempts to reach the lower right corner of the grid (labeled "Finish" in the following image).

How many different paths are there in total?

For example, the image above is a 7 x 3 grid. How many possible paths are there?

Note: the values of m and n are not more than 100.

Example 1:

Input: M = 3, n = 2

Output: 3

Explanation:

Starting from the upper left corner, there are a total of 3 paths to the lower right corner.

Right-> right-> Down right-> Down-> right Down-> right-> right

Example 2:

Input: M = 7, n = 3

Output: 28

Positive thinking

Let's think about it in a normal way of thinking, when you are at the starting point, you have two choices, right or down, unless you are in the bottom row or the rightmost column, then you have only one choice (for example, in the bottom row. You can only go right). Other positions, you have two choices.

So, based on this idea, we can write code:

Class Solution {public int uniquePaths (int m, int n) {/ / Special case: the starting point is the end if (m = = 1 & & n = 1) {return 1;} / / the end point is (1 return 1), and the end point is (m int n) return walk (1 int 1, m int n);} public int walk (int x, int y, int m, int n) {/ / is already at the end point if (x > = m & y > = n) {return 0 } / / in the bottom row or the rightmost row of if (x > = m | | y > = n) {return 1;} / / go down, how many ways are there int down = walk (x ~ * ~ y + 1, m ~ ~ n); / / how many kinds of walks are there int right = walk (x + 1, y, m ~ (n)); / / how many kinds of walks are there from the current (x ~ ~ ()) to (m ~ () ~ n), how many ways are there (return down + right)? }}

Optimize

Let's consider whether there is any room for optimization in this way of writing.

You should find at a glance that the first judgment if of the walk method (x > = m & & y > = n) can never be true, because the next judgment if (x > = m | | y > = n) is already a critical point, and there is already a return value directly, which is impossible to reach x > = m & y > = n. Therefore, the judgment can be deleted.

Suppose we start from the position of (1) and the end point is (3), what are the ways to get to the middle point (2)? Two kinds, first to (1) and then to (2), or (2) to (2) and then to (2)

Therefore, according to the way we wrote above, from (2p2) to the end (3p3), we will count twice, although this idea itself is correct, but this situation should be optimized. Because there are only 6 paths from (1) to (3), but there are already 2 repetitive paths, so as m and n become larger and larger, there will be more and more intermediate points, so there will be more and more repetitive paths.

This is that the front choice will have an impact on the latter choice, even if the latter choice is the same, but because the previous choice is different, it is also considered to be a different choice.

Obviously, the latter choice is more unique, and if we make the choice first, we can reduce the number of recalculation. Therefore, we can try the reverse way of thinking.

Reverse train of thought

If we do not start from the starting point, but go back from the end to the starting point. Suppose the end point is (3p3), it can only be directly reached by (2p3) and (3mag2), (2p3) can only be directly reached by (2p2) and (1p3), (1p3) can only be directly reached by (1p2), (1p2) can only be directly reached by (1jue 1), so (1p3) can only be directly reached by (1p1).

We can draw a rule: except for the points in the leftmost column and the top row, which can only be reached directly from the starting point (1), the other points (xmemy) are directly reached by (xmai 1) and (xmemy 1).

So, according to this idea, we can write code:

Class Solution {public int uniquePaths (int m, int n) {int [] [] result = new int [m] [n]; int j; for (int I = 0; I

< m; i++) { for (j = 0; j < n; j++) { if (i == 0 || j == 0) { // 最上面一排的点和最左边一列的点，只能由(1,1)到达 result[i][j] = 1; } else { // 其他的点都可以由左边的点和上面的点到达 result[i][j] = result[i - 1][j] + result[i][j - 1]; } } } return result[m - 1][n - 1]; }} 其实这样的想法就已经是动态规划的范畴了，我们看看维基上的定义 动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 一开始我感觉很像分治法，因为都需要将一个大问题分解为子问题，但分治法最终会将子问题合并，但动态规划却不用。 优化 我们考虑一下，这种写法，有没有可以优化的地方。 首先是空间上的优化，我们一定要用二维数组吗？可以用一维数组代替吗？ 答案是肯定的，因为每个点的计算只和左边与上边相邻的点有关，因此，不需要更加久远的点。 一维数组 假如只用一维数组，那么只需要存储上一排的结果，如果计算到下一排的时候，则依次替换，代码为： class Solution { public int uniquePaths(int m, int n) { int[] dp = new int[m]; int j; for(int i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(j == 0) { dp[j] = 1; } else { // 其他的点都可以由左边的点和上面的点到达 dp[j] += dp[j-1]; } } } return dp[m-1]; }} 这样的优化，差不多就结束了。那我们是否可以从思路上进行优化呢？ 组合数 因为我们只有向右或向下两种选择，而我们一共要走的路径其实是(m-n-2)，其中有(m-1)的路径是向右，(n-1)的路径是向下，其实可以转变为： 从(m-n-2)中挑出(m-1)，即组合数C((m-n-2), (m-1))的值 那么我们可以写出代码： class Solution { public int uniquePaths(int m, int n) { // 用double，因为计算出的数值会很大 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.