Example of dynamic programming 3 leetcode 55

Jump Game

Translation work

Give you an array of integers , you （ Take frogs for example ） Initially at the beginning of the matrix , Each element in the array represents the maximum number of hops you can jump at the current position .

If you can jump to the last position , return true, otherwise , return false.

Example 1：

Input ：nums = [2,3,1,14]

Output ：true

explain ： from 0 Jump to the 1, Again from 1 jump 3 Step to the last position

Example 2：

Input ：nums = [3,2,1,0,4]

Output ：false

explain ： You'll end up in the third position （ from 0 Start ）, The maximum number of hops at this position is 0, It is impossible to jump to the last position .

Limit ：

1 <= nums.length <= 10^4

0 <= nums[i] <= 10^5

1. Determine the state of

1） The last step

If the frog could jump to the last stone n-1, Consider the last step it takes , This step from the stone i Jump over ,i<n-1.

This requires two conditions to be met ：

a. Frogs can jump to rocks i

b. The last step does not exceed the maximum number of hops ：n-1-i <= ai

2) Sub problem

Need to know if a frog can jump to a stone i（i<n-1)

2. Transfer equation

set up f[j[ It means whether the frog can jump to the stone j

f[j] = OR{0<= j <i}(f[j] AND j+a[j] >= j)

3. Initial and boundary conditions

f[0] = true

4. Computation order

f[0]] = true

Calculation f[1],f[2]……f[n-1]

The answer is f[n-1]

Example

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

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];		
}

/*
LintCode116 Jump Game
 Yes n The stones are in x The shaft 0,1,……,n-1 Location 
 A frog is in the stone 0, Want to jump to the stone n-1
 If the frog is in the i On a stone , It can jump up to a distance to the right ai
 Ask the frog if he can jump to the stone n-1
*/

bool JumpGame( int a[],int n) {
	bool *f = new bool[n];
	f[0] = true;
	for (int i = 1; i < n; i++) {
		f[i] = false;
		for (int j = 0; j < i; j++) {
			if (f[j]==true && j + a[j] >= i) {
				f[i] = true;
				break;
			}
		}
	}
	return f[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);
	*/
	//JumpGame
	int a[] = { 2,3,1,1,4 };
	int lena = sizeof(a) / sizeof(int);
	cout << boolalpha << JumpGame(a, lena) << endl;
	return 0;
}