f(x) = cost(x) + max( f(x-1), f(x-2), ... f(x-k))

一开始的做法, 是for循环在找最大值. 这里就直接在大数据测试用例就超时了. 这里的时间复杂度就 O(nk) 这里n和k都是输入且range也差不多, 可以都当作n 相当于 O(n^2)

优化的方案是 对于任意一位置i, 我们只关心之前k的位置的, 能取得最大收益的那个值, 就是这里的max 可以考虑用一个能排序的数据结构, 可以用堆(heap) java中对应的就是 PriorityQueue

唯一需要注意的就是, 堆顶的元素, 如果其位置距离当前位置大于k, 那么我们需要pop.

那你可能会问, 那么距离大于k, 其不在堆顶的怎么办? 答: 我们不care..不会影响时空复杂度.

 1class Solution {
 2    public int maxResult(int[] nums, int k) {
 3        if (nums == null || nums.length == 0) return 0;
 4        
 5        int n = nums.length;
 6        
 7        int[] dp = new int[n];
 8        Arrays.fill(dp, Integer.MIN_VALUE);
 9        dp[0] = nums[0];
10        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[0]-a[0]);
11        pq.offer(new int[]{nums[0], 0});
12        for (int i = 1; i < n; i++) {
13            // remove old one, pos before (-inf, i-k), has no chance to jump here
14            while(!pq.isEmpty() && pq.peek()[1] < i-k ) {
15                pq.poll();
16            }
17            // jump from the biggest one from [i-k,i-1]
18            dp[i] = nums[i] + dp[pq.peek()[1]];
19            pq.offer(new int[]{dp[i], i});
20        }
21        return dp[n-1];
22    }
23}

每个元素放入pq最多一次，pop out最多一次，每次heapify是O(logn) 构建这个堆是 O(n) 空间是 O(n)

做DP用的数据是O(n), 所以最终的时间复杂度, 就是这个循环体的时间复杂度, O(nlogn)

空间复杂度是O(n)