LintCode 622. Frog Jump

http://www.lintcode.com/en/problem/frog-jump/


Suitable for the bottom-up DP approach:
the first jump must be 1 unit.
the other jumps can be multiple units.

That mean a if-else clause is needed inside the loop.
Then the multiple units call for a collection, and we don't want duplication, so a HashSet would be ideal.

There you go:

	public class Solution {
	/*
	* @param stones: a list of stones' positions in sorted ascending order
	* @return: true if the frog is able to cross the river or false
	*/
	boolean canCross(int[] stones) {
	// filter abnormal cases
	if (stones == null || stones.length == 0) {
	return true;
	}
	int len = stones.length;
	boolean[] dp = new boolean[len];
	ArrayList<HashSet<Integer>> ksList = new ArrayList<>(len + 1);
	for (int i = 0; i < len; i++) {
	ksList.add(new HashSet<>());
	}
	for (int i = 0; i < len; i++) {
	if (i == 0) {
	dp[0] = true;
	} else {
	if (i == 1) {
	if (stones[1] - stones[0] == 1) {
	dp[1] = true;
	ksList.get(1).add(1);
	} else {
	return false;
	}
	}
	for (int to = i + 1; to < len; to++) {
	int require = stones[to] - stones[i];
	if (ksList.get(i).contains(require - 1) || ksList.get(i).contains(require) || ksList.get(i).contains(require + 1)) {
	dp[to] = true;
	ksList.get(to).add(require);
	}
	}
	}
	}
	// return the final result
	return dp[len - 1];
	}
	}

view raw LintCode 622. Frog Jump - LintCode.java hosted with ❤ by GitHub