frog v2ex

Solution.java

/*
V2不能改内容所以直接这里改了: maxqueue的做法实际上是错误的; 这题并不需要这么复杂; 
直接把dp算出来, 然后最后单独走一个min_step的循环, 找一个最大值就行了; 
在算每一个dp[i]的时候, 不能包含这个反向min_step的循环的最大值. 只能最后返回之前算这个; 
*/

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;
    }
}