[LeetCode]Frog Jump

这题BFS/DFS当然是可以做的，但是会超时。优化的话我们考虑DP的方法，DP[i][j]表示从处在i坐标的石头开始，并且上一次走了j步的情况下，我们能否最终到达终点。那么我们有递推公式：

• DP[i][j] = DP[i + j][j] | DP[i + j + 1][j + 1] | DP[i + j - 1][j - 1], if i > 1
• DP[i][j] = DP[i + j][j] | DP[i + j + 1][j + 1], if i == 1
• DP[i][j] = DP[i + j + 1][j + 1], if i == 0

在实现的时候，由于step的值可能很大，开出来的二维矩阵太浪费空间，我们用memorization的写法。时间复杂度，空间复杂度均为O(n ^ 2)，代码如下

	class Solution {
	public:
	bool canCross(vector<int>& stones) {
	int len = stones.size();
	//memo[i][j] represent if we can reach end start at stone of postion i and take j steps
	unordered_map<int, unordered_map<int, bool>> memo;
	unordered_set<int> positions;
	for(auto& stone : stones)positions.insert(stone);
	return dfs(positions, 0, 0, stones.back(), memo);
	}
	private:
	bool dfs(unordered_set<int>& stones, int pos, int step, int target, unordered_map<int, unordered_map<int, bool>>& memo)
	{
	if(pos >= target)return pos == target;
	if(memo.find(pos) != memo.end() && memo[pos].find(step) != memo[pos].end())
	return memo[pos][step];
	bool canReachEnd = false;
	if(stones.find(pos + step + 1) != stones.end())
	canReachEnd = canReachEnd | dfs(stones, pos + step + 1, step + 1, target, memo);
	if(step >= 1 && stones.find(pos + step) != stones.end())
	canReachEnd = canReachEnd | dfs(stones, pos + step, step, target, memo);
	if(step > 1 && stones.find(pos + step - 1) != stones.end())
	canReachEnd = canReachEnd | dfs(stones, pos + step - 1, step - 1, target, memo);
	memo[pos][step] = canReachEnd;
	return canReachEnd;
	}
	};

view raw Frog Jump_1.cpp hosted with ❤ by GitHub

另一种DP的写法，我们用DP[i]表示所有可以从起始点达到位于坐标i处石头的步数，也就是DP[i]是一个list。我们在更新的时候从前往后更新，比如我们在i的时候，遍历DP[i]的值算出其可达到所有位置j1, j2, j2...，然后更新DP[jx]的值即可。我们同样是用map来存，因为可能非常稀疏。时间复杂度，我们遍历每一个stone，每一个stone最多可能从n - 1个其他的stone到达，时间复杂度O(n ^ 2)，代码如下：

	class Solution {
	public:
	int minStickers(vector<string>& stickers, string target) {
	int n = target.size(), len = stickers.size();
	//dp represents minimum sticker required for current state
	//state is a binary number where each bit represents if corresponding char appears
	vector<int> dp(1 << n, -1);
	dp[0] = 0;
	for(int i = 0; i < 1 << n; ++i)
	{
	if(dp[i] == -1)continue;
	for(auto sticker : stickers)
	{
	int state = i;
	for(int j = 0; j < sticker.size(); ++j)
	{
	for(int k = 0; k < n; ++k)
	{
	//if we have two same chars, two 'a's
	//if the first 'a' is matched, we don't
	//want the second 'a' to match the same
	//position in i again
	if((state >> k & 1) == 1)continue;
	if(sticker[j] == target[k])
	{
	//if current char c in sticker is matched
	//it shouldn't match another char in i again,
	//we just break
	state |= 1 << k;
	break;
	}
	}
	}
	if(dp[state] == -1 || dp[i] + 1 < dp[state])
	dp[state] = dp[i] + 1;
	}
	}
	return dp[(1 << n) - 1];
	}
	};

view raw Stickers to Spell Word_2.cpp hosted with ❤ by GitHub