leet1340.jump-game-v

1340. 跳跃游戏 V

思路

按照题目给的提示，暴力动态规划，加入记忆化避免重复计算。

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        const int n = arr.size();
        vector<int> dp(n, 0);
 
        function<int(int)> calc = [&](int idx) {
            if (dp[idx] > 0) return dp[idx];
 
            int beg = max(0, idx - d);
            int end = min(n - 1, idx + d);
            int rgmx_idx = idx;
            int lv_max = 0;
            for (int j = idx + 1; j <= end; ++j) {
                if (arr[j] >= arr[rgmx_idx]) {
                    rgmx_idx = j;
                    continue;
                }
                if (arr[j] < arr[rgmx_idx]) {
                    if (rgmx_idx != idx) continue;
                    lv_max = max(lv_max, calc(j));
                }
            }
            rgmx_idx = idx;
            for (int j = idx - 1; j >= beg; --j) {
                if (arr[j] >= arr[rgmx_idx]) {
                    rgmx_idx = j;
                    continue;
                }
                if (arr[j] < arr[rgmx_idx]) {
                    if (rgmx_idx != idx) continue;
                    lv_max = max(lv_max, calc(j));
                }
            }
            // 把中间结果存起来，减少重复计算
            dp[idx] = 1 + lv_max;
            return dp[idx];
        };
 
        for (int i = 0; i < n; ++i) {
            dp[i] = calc(i);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

高性能解（待研究）

todo

int ans[1005], ord[1005];
 
class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        const int n = size(arr);
        for (int i = 0; i < n; i++) {
            ans[i] = 0;
            ord[i] = i;
        }
 
        sort(ord, ord+n, [&arr](int a, int b) -> bool {
            return arr[a] < arr[b];
        });
        int r = 0;
        for (int i = 0; i < n; i++) {
            const int k = ord[i];
            int m = 0;
            for (int j = k-1; j >= 0 && j >= k-d; j--) {
                if (arr[j] >= arr[k]) { break; }
                m = max(m, ans[j]);
            }
            for (int j = k+1; j < n && j <= k+d; j++) {
                if (arr[j] >= arr[k]) { break; }
                m = max(m, ans[j]);
            }
            ans[k] = 1+m;
            r = max(r, ans[k]);
        }
        return r;
    }
};