Dynamic programming example 2 leetcode62 unique paths

LeetCode Unique Paths

 

Translation work

There is a robot m*n On the square of . The robot was initially in the upper left corner of the grid (grid[0][0]), The robot wants to reach the lower right corner of the grid (grid[m-1][n-1]), The robot can only go right or down at any time .

Give two integers m and n, Returns the number of paths the robot has reached the lower right corner .

Test examples are given , The result can only be less than or equal to 2*10^9

Example 1：

Input ：m = 3,n = 7

Output ：28

Example 2：

Input ：m = 3, n = 2

Output ：3

explain ： From the top left corner , Yes 3 This way to the lower right corner

angle ：

1. Right -> Next -> Next

2. Next -> Next -> Right

3. Next -> Right -> Next

Limit ：

1<=m,n<=100

With m = 8, n = 4 For example

1. Determine the state of

1） The last step

No matter how the robot gets to the lower right corner , There's always one last move ： To the right or down

The coordinates of the lower right corner are set to (m-1,n-1).

So the previous robot must have been (m-2,n-1) perhaps (m-1,n-2)

2） Sub problem

that , If the robot has x Go from the top left corner to (m-2,n-1), Yes Y Go from the top left corner to (m-1,n-2), The robot has X+Y There are ways to get to (m-1,n-1)

notes ： The principle of addition ：a. No repetition b. There is no omission

Sub problem ： How many ways do robots go from the upper left corner to (m-2,n-1) and (m-1,n-2), Two coordinates, two variables , Therefore, the status can be set to f[i][j] There are many ways for robots to go from the upper left corner to (i,j).

2. Transfer equation

For any lattice (i,j)

f[i][j]  =  f[i-1][j]  +  f[i][j-1]

3.c Initial and boundary conditions

Initial conditions f[0][0] = 1

4. Computation order

f[0][0] = 1

Computation first 0 That's ok ：f[0][0],f[0][1],……,f[0][n-1]

……

Computation first m-1 That's ok ：f[m-1][0],f[m-1][1],……,f[m-1][n-1]

answer f[m-1][n-1]

notes ： Time complexity ：O(mn)

        Spatial complexity ：O(mn)

Example ：

#include<iostream>
#include<malloc.h>
#include<vector>

using namespace std;

//LintCode;Coin Change
//3 Grow coins 2 element  5 element  7 element , Buy a Book 27 element 
// How to pay with the least combination of coins , There is no need for the other party to pay f(x) Said to buy one 27 Yuan book to make up the least coin 


/******66656565{2,5,7} ***  27*/
/*
int CoinChange(int A[], int m) {
	int MAXN = 32001;
	int **f = new int[m+1];
	f[0] = 0;
	int lenA = 0;
	for (int i = 0; A[i] >= 0; i++) {
		lenA++;
	}
	int i, j;
	for (i = 1; i <= m; i++) {  //1 2 3...m
		f[i] = MAXN;
		for ( j = 0; j < lenA; j++) {  //2 5 7
			if (i >= A[j] && A[i - A[j]] != MAXN) { // The required amount is greater than the face value and the current face value can make up the required amount 
				f[i] = f[i] < (f[i - A[j]] + 1) ?  f[i] : (f[i - A[j]] + 1) ;
			}
		}
	}
	if (f[m] == MAXN) {
		f[m] = -1;
	}
	return f[m];
}
*/
/*
LeetCode 62 Unique Paths
 Given m That's ok n Column grid , There's a robot from the top left (0,0) set out , Each step can be down or down 
 How many different ways to get to the lower right corner 
*/

int UniquePaths(int m, int n) {
	std::vector<vector<int > > f(m);
	for (int i = 0; i < m; i++) {
		f[i].resize(n);
	}
	for (int i = 0; i < m; i++) { // That's ok 
		for (int j = 0; j < n; j++) {// Column 
			if (i == 0 || j == 0) {
				f[i][j] = 1;
			}
			else {
				f[i][j] = f[i - 1][j] + f[i][j - 1];
			}

		}
	}
	return f[m-1][n-1];		
}


int main() {
	//Coinchange
	/*
	int A[] = { 2,5,7 };
	int m = 27;
	cout<<CoinChange(A,m);
	*/
	//UniquePaths
	int m = 8, n = 4;
	cout << UniquePaths(m, n);

	return 0;
}