day23打卡

122 买股票最大时机II

class Solution {
public:
int maxProfit(vector& prices) {
vector<vector> dp(prices.size(), vector(2,0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < prices.size(); ++i)
{
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
}
return dp[prices.size()-1][1];
}
};

55. 跳跃游戏

class Solution {
public:
bool canJump(vector& nums) {
if(nums.size() == 1)
{
return true;
}
int cover = 0;
for(int i = 0; i <= cover; ++i)
{
if(i + nums[i] > cover)
{
cover = i + nums[i];
if(cover >= nums.size() - 1)
{
return true;
}
}
}
return false;
}
};

跳跃游戏II

class Solution {
public:
int jump(vector& nums) {
if (nums.size() == 1) return 0;
int cur = 0;
int next = 0;
int ret = 0;
for(int i = 0; i < nums.size(); ++i)
{
next = max(nums[i] + i, next);
if(i == cur)
{
if(cur != (nums.size() - 1))
{
++ret;
cur = next;
if(cur >= (nums.size()-1))
{
break;
}
}
else
{
break;
}
}
}
return ret;
}
};