LeetCode 55. Jump Game

首先这是个动态规划的题……

我竟然一开始用了dfs做……

最后当然是time limit exceeded.

你直接无脑dfs当然可以。

贴下代码：

#include <iostream> 
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn=1e3+5;

bool dfs(int i,int len,vector<int>& a){
	if(i>=len) return 0;
	else if(i==len-1) return 1;
	else if(a[i]==0&&i!=len-1) return 0;
	else {
		for(int j=1;j<=a[i];j++){
			if(dfs(i+j,len,a)) return 1;
			else return 0;
		}
	}
}
int main(){
//	int b[]={2,3,1,1,4};
	int b[]={3,2,1,0,4};
	vector<int> a(b,b+5);
	cout<<dfs(0,a.size(),a)<<endl;
}

那我们转念一想，子问题果然重叠。设f(n)函数表示下标为n的元素是否能达到。

那么

f(n)=f(上一个元素)，状态转移方程。

f(0)=true，边界条件。

同一个元素可以有很多个上一个状态，这个题比较特殊，我们知道它的起点总是下标为0的元素，那么我们选择离0最近的那个元素作为下标为n元素的上一个状态就好了，用了一点贪心的思想，顺便剪枝嘛。f(0)总是true，这个问题可以换一种问法，就是，我们的前一个状态最终能不能达到f(0)。

AC code:

class Solution {
public:
   
    bool canJump(vector<int>& a) {
        int len=a.size();
        int goal=len-1;
        for(int i=len-2;i>=0;i--){
            if(i+a[i]>=goal)
                goal=i;
        }
        if(goal==0) return 1;
        else return 0;
    }
};