LeetCode.213.55.45.62(动态规划)

213.打家劫舍-ii

class Solution {
  public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        /* if (n <= 1) {
            return nums[0];
        }
        int Max = 0;
        for (int i = 0; i < n; i++) {
            vector<int> path(n, 0);
            path[0] = nums[i];
            path[1] = max(nums[(i + 1) % n], path[0]);
            int pathMax = path[1];
            for (int j = i + 2; j < i - 1 + n; j++) {
                int q = 0;
                for (int k = i; k < j - 1; k++) {
                    q = max(q, nums[j % n] + path[k - i]);
                }
                path[j - i] = q;
                pathMax = max(pathMax, q);
            }
            Max = max(Max, pathMax);
        }
        return Max;
        // 75/75 cases passed (16 ms)
        // Your runtime beats 32.87 % of cpp submissions
        // Your memory usage beats 5 % of cpp submissions (8 MB) */
        if (n <= 2)
            return n == 2 ? max(nums[0], nums[1]) : nums[0];
        vector<int> path(n, 0);
        path[0] = nums[0];
        path[1] = max(nums[1], path[0]);
        int Max = path[1];
        for (int i = 2; i < n - 1; i++) {
            int q = 0;
            for (int j = 0; j < i - 1; j++) {
                q = max(q, nums[i] + path[j]);
            }
            path[i] = q;
            Max = max(Max, q);
        }
        vector<int>(n, 0).swap(path);
        path[0] = nums[1];
        path[1] = max(nums[2], path[0]);
        Max = max(Max, path[1]);
        for (int i = 3; i < n; i++) {
            int q = 0;
            for (int j = 1; j < i - 1; j++) {
                q = max(q, nums[i] + path[j - 1]);
            }
            path[i - 1] = q;
            Max = max(Max, q);
        }
        return Max;
        // 75/75 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 60.49 % of cpp submissions (7.6 MB)
        //*没必要因为循环数组而循环判断，本质就是头一个和最后一个不同时取，判断两下就好了
    }
};

55.跳跃游戏

class Solution {
  public:
    bool canJump(vector<int> &nums) {
        /* if (nums.size() == 1)
            return 1;
        if (nums[0] == 0)
            return 0;
        for (int i = nums.size() - 2; i >= 0; i--)
            if (nums[i] + i >= nums.size() - 1) {
                nums.pop_back();
                return canJump(nums);
            }
        return 0; */
        // 169/169 cases passed (44 ms)
        // Your runtime beats 89.28 % of cpp submissions
        // Your memory usage beats 28.54 % of cpp submissions (47.2 MB)
        if (nums.size() == 1)
            return 1;
        if (nums[0] == 0)
            return 0;
        int energy = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (energy <= 0)
                return 0;
            energy = max(nums[i], energy - 1);
        }
        return 1;
        // 169/169 cases passed (44 ms)
        // Your runtime beats 89.28 % of cpp submissions
        // Your memory usage beats 72.3 % of cpp submissions (47.1 MB)
        /* 想象你是那个在格子上行走的小人，格子里面的数字代表“能量”，你需要“能量”才能继续行走。

        每次走到一个格子的时候，你检查现在格子里面的“能量”和你自己拥有的“能量”哪个更大，取更大的“能量”！
        如果你有更多的能量，你就可以走的更远啦！~ */
        //真的难想
    }
};

45.跳跃游戏-ii

class Solution {
  public:
    int jump(vector<int> &nums) {
        int n = nums.size();
        /* vector<int> path(n, INT_MAX - 1);
        path[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            int q = INT_MAX - 1;
            for (int j = i + 1; j <= i + nums[i] && j < n; j++)
                q = min(q, path[j] + 1);
            path[i] = q;
        }
        return path[0];
        // 109/109 cases passed (196 ms)
        // Your runtime beats 18.01 % of cpp submissions
        // Your memory usage beats 5.12 % of cpp submissions (16.8 MB) */
        int curDistance = 0;  // 当前覆盖最远距离下标
        int ans = 0;          // 记录走的最大步数
        int nextDistance = 0; // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);
            // 更新下一步覆盖最远距离下标
            if (i == curDistance) {
                // 遇到当前覆盖最远距离下标
                if (curDistance != nums.size() - 1) {
                    // 如果当前覆盖最远距离下标不是终点
                    ans++;
                    // 需要走下一步
                    curDistance = nextDistance; // 更新当前覆盖最远距离下标（相当于加油了）
                    if (nextDistance >= nums.size() - 1)
                        break; // 下一步的覆盖范围已经可以达到终点，结束循环
                } else
                    break; // 当前覆盖最远距离下标是集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
        // 109/109 cases passed (4 ms)
        // Your runtime beats 99.64 % of cpp submissions
        // Your memory usage beats 26.76 % of cpp submissions (16.2 MB)
        //*要用贪心算法
    }
    // [2,3,1,1,4]
    // 0 2 curDistance = 2 ans=1 nextDistance=2
    // 1 3 curDistance = 2 ans=1 nextDistance=4
    // 2 1 curDistance = 4 ans=2 nextDistance=4
};

62.不同路径

class Solution {
  public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> record(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
            record[i][n - 1] = 1;
        for (int i = 0; i < n; i++)
            record[m - 1][i] = 1;
        for (int i = m - 2; i >= 0; i--)
            for (int j = n - 2; j >= 0; j--)
                record[i][j] = record[i + 1][j] + record[i][j + 1];
        return record[0][0];
        // 63/63 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 56.15 % of cpp submissions (6.3 MB)
    }
};