Skip to content

Instantly share code, notes, and snippets.

@vegito2002 vegito2002/Solution.java
Last active Mar 27, 2018

Embed
What would you like to do?
frog v2ex
/*
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.