V2EX_JumpingFrog [source code]

public class V2EX_JumpingFrog {
static
/******************************************************************************/
class Solution {
    int solve (int[] staircase, int[] possible_steps) {
        int min_step = Integer.MAX_VALUE, N = staircase.length;
        for (int step : possible_steps)
            min_step = Math.min (min_step, step);
        if (min_step > N)
            return 0;
        int[] dp = new int[N];
        for (int i = -1 + min_step; i < N; i++) {
            int cur = Integer.MIN_VALUE;
            for (int step : possible_steps) {
                if (i - step >= -1)
                    cur = Math.max (cur, i - step >= 0 ? dp[i - step] : 0);
            }
            dp[i] = cur + staircase[i];
        }
        int res = Integer.MIN_VALUE;
        for (int i = N - 1; (N - 1) - i < min_step; i--)
            res = Math.max (res, dp[i]);
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        V2EX_JumpingFrog.Solution tester = new V2EX_JumpingFrog.Solution();
        int[][] inputs = {
            {11, 22, 44, 5, 12, 34, 55, 45, 23, 64}, {3,4,5}, {163},
            {11, 22, 44, 5, 12, 34, 55, 45, 23, 64}, {300}, {0},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println (Printer.separator ());
            int[] staircase = inputs[3 * i], possible_steps = inputs[3 * i + 1];
            int ans = inputs[3 * i + 2][0], output = tester.solve (staircase, possible_steps);
            System.out.printf ("%s and %s\n%s, expected: %d\n", 
                Printer.array (staircase), Printer.array (possible_steps), Printer.wrap (output + "", output == ans ? 92 : 91), ans
            );
        }
    }
}

还能进一步优化: 第二个循环, 求min_step这个window里面的最小值, 这个可以用一个min_heap来维护; 一个固定size的窗口的min用一个minheap来维护, 之前是见过的;

大概实现了一下, 我用的方法跟当时看的awice的有点区别, 我这个是直接ad-hoc的做法, 用composition来完成; awice当时给的做法, 还有泛型, 是一个更加generic的做法;

这个是第一版的代码:

这个优化降低的是min_step级别的常数级别的factor; 如果min_step很大, 比如达到了O(N)级别, 那么这个优化还是很有效果的;

上面说的maxqueque做法代码:

class Solution {  
    int solve (int[] staircase, int[] possible_steps) {  
        int min_step = Integer.MAX_VALUE, N = staircase.length;  
        for (int step : possible_steps)  
            min_step = Math.min (min_step, step);  
        if (min_step > N)  
            return 0;  
        int[] dp = new int[N];  
        MaxQueue min_queue = new MaxQueue ();  
        for (int i = 0; i < min_step; i++)  
            min_queue.addLast (0);  
        for (int i = -1 + min_step; i < N; i++) {  
            int cur = Integer.MIN_VALUE;  
            for (int step : possible_steps) {  
                if (i - step >= -1)  
                    cur = Math.max (cur, i - step >= 0 ? dp[i - step] : 0);  
            }  
            cur += staircase[i];  
            cur = Math.max (cur, min_queue.windowMax ());  
            min_queue.removeFirst ();  
            min_queue.addLast (cur);  
            dp[i] = cur;  
        }  
        return dp[N - 1];  
    }  

    static class MaxQueue {  
        Deque<Integer> maxes;  
        Deque<Integer> window;  

        MaxQueue() {  
            maxes = new ArrayDeque<> ();  
            window = new ArrayDeque<> ();  
        }  

        void addLast (int x) {  
            window.addLast (x);  
            while (maxes.peekLast() != null && x > maxes.peekLast ())  
                maxes.removeLast ();  
            maxes.addLast (x);  
        }  

        int removeFirst () {  
            int x = window.removeFirst ();  
            if (x == maxes.peekFirst ())  
                maxes.removeFirst ();  
            return x;  
        }  

        int windowMax () {  
            return maxes.peekFirst ();  
        }  
    }  
}

但是!!!

这个做法实际上是错的; i循环里面的第二个min_step循环, 实际上根本不需要! 事实上, 不仅不需要, 而且不应该; 按照root level involvement的思路, 这题在每一个node的位置, 只要考虑ending at this的path就行了, 然后最后所有的算完了, 再走一个单独的min_step循环(从右到左)找到一个最大值就行了; 自己想想为什么不能每一个node都有这个min_step循环, 这个bug稍微有点subtle;

Problem Description

一个青蛙跳台阶
每个台阶上有个随机数, 比如:

staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64]
给定 n 个台阶和可能跳的步数,比如:

possible_steps = [3,4,5]
对跳到的台阶的数求和,比如:

step_sequence = [3,4] , sum = 44+55 = 99
step_sequence = [4,4,4] , sum = 5+45+(超出台阶算 0) = 50
问和最大的时候是多少? 比如:

best_step_sequence = [3,4,4] , best_sum = 44+55+64 = 163
Example:

Input:

staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64]
possible_steps = [3,4,5]
Output

163