5.10 Notes

5.4-5.10 Learning Notes

Leetcode

跳跃游戏

第一题求能否到达终点，第二题求到达终点的最小步数
两题都可以用贪心做

I

题解

1. 如果某一个作为起跳点的格子可以跳跃的距离是 3，那么表示后面3 个格子都可以作为 起跳点。
2. 可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
3. 如果可以一直跳到最后，就成功了。

II

我的代码：

• 使用cnt数组记录跳到某一个位置所需的最小步数

class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int r = 0;
        int n = nums.size();
        int cnt[n];
        memset(cnt, -1, sizeof(cnt));
        cnt[0] = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (i + nums[i] <= r)
                continue;
            for (int j = r + 1; j < n && i + nums[i] >= j; j++)
                cnt[j] = cnt[i] + 1;
            r = i + nums[i];
            if (r >= n)
                break;
        }
        return cnt[n - 1];
    }
};

精简后的代码（题解）：

class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int r = 0;
        int n = nums.size();
        int step = 0;
        int end = 0;
        for (int i = 0; i < nums.size() - 1; i++)
        {
            r = max(r, i + nums[i]);
            if (i == end)
            {
                end = r;
                ++step;
            }
        }
        return step;
    }
};

最低票价

初始思路：
dp[i]表示完成前i个旅行计划所需要的最低消费
$dp[i]=\min{f[j]+costs[k]}$, $k=0,1,2$ ,$days[j]+t[k]>=days[i]$
$t[3]={1,7,30}$

这样定义dp方程的话是有后效性的。因为第i个旅行计划之前的消费都是确定的，有点类似贪心，没有考虑到当前还剩多少天的通行证。

正解：
dp[i]表示前i天所需要的最低消费

• 如果当天不在计划内$dp[i]=dp[i-1]$
• 如果在计划内$dp[i]=\min{dp[i-1]+costs[0],dp[i-7]+costs[1],dp[i-30]+costs[2]}$

class Solution {
public:
    const int inf=1<<30;
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int ticket[3]={1,7,30};
        int n=days.size();
        vector<int> dp(days[n-1]+1,0);
        for (int i=0;i<n;i++)
            dp[days[i]]=-1;
        for (int i=1;i<=days[n-1];i++)
        {
            if (dp[i]==0)
                dp[i]=dp[i-1];
            else
            {
                dp[i]=min({dp[max(i-1,0)]+costs[0],dp[max(i-7,0)]+costs[1],dp[max(i-30,0)]+costs[2]});
            }
        }
        return dp[days[n-1]];
    }
};