动态规划(Dynamic Programming) 例题3 LeetCode 55

Jump Game

翻译工作

给你一个整数数组，你（以青蛙为例）最初在矩阵的开始处，数组中每个元素代表你在当前位置所能跳出的最大跳数。

如果你能跳到最后的位置，返回true，否则，返回false。

示例1：

输入：nums = [2,3,1,14]

输出：true

解释：从0跳到1，再从1跳3步到达最后位置

示例2：

输入：nums = [3,2,1,0,4]

输出：false

解释：你最终会停在第三个位置（从0开始），该位置的最大跳数是0，不可能跳到最后位置。

限制：

1 <= nums.length <= 10^4

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

1.确定状态

1）最后一步

如果青蛙能够跳到最后一块石头n-1，考虑它跳的最后一步，这一步从石头i跳过去，i

这需要两个条件满足：

a.青蛙可以跳到石头i

b.最后一步不超过跳跃的最大跳数：n-1-i <= ai

2) 子问题

需要知道青蛙能否跳到石头i（i

2.转移方程

设f[j[表示青蛙能否跳到石头j

f[j] = OR{0<= j = j)

3.初始条件和边界条件

f[0] = true

4.计算顺序

f[0]] = true

计算f[1],f[2]……f[n-1]

答案是f[n-1]

示例

#include
#include
#include
#include

using namespace std;

//LintCode;Coin Change
//3种硬币2元 5元 7元，买一本书27元
//如何用最少的硬币组合正好付清，不需要对方付清f(x)表示买一本27元的书凑出最少的硬币







int UniquePaths(int m, int n) {
	std::vector > f(m);
	for (int i = 0; i < m; i++) {
		f[i].resize(n);
	}
	for (int i = 0; i < m; i++) { //行
		for (int j = 0; j < n; j++) {//列
			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];		
}



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
	
	//UniquePaths
	
	//JumpGame
	int a[] = { 2,3,1,1,4 };
	int lena = sizeof(a) / sizeof(int);
	cout << boolalpha << JumpGame(a, lena) << endl;
	return 0;
}