leetcode 55. Jump Game (dp)
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
思路:dp[i]表示能否到达位置i...无脑dp即可。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月11日 星期二 19时33分51秒
4File Name :55.cpp
5************************************************ */
6class Solution {
public:
1 bool canJump(vector<int>& nums) {
2 int n = nums.size();
3 if (n==0) return false;
4 vector<int>dp(n,false);
5 dp[0] = true;
6 for ( int i = 0 ; i < n ; i++)
7 {
8 if (dp[i])
9 {
10 int r = min(i+nums[i],n-1);
11 for ( int j = i+1 ; j <=r ; j++)
12 dp[j] = true;
13 }
14 }
15 return dp[n-1];
}
};