[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)，代码如下

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