一、题目

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。

给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。

开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

点击查看原题

二、思路

此问题很容易想到是动态规划，因为青蛙现在的所站的地点，一定是从上一个（或上几个）点一下子跳过来的，就化简成为了子问题，假设dp[i]（TreeSet类型）是跳第i步所有有可能的步长，令val=stones[i]-stones[j]，val表示从j跳到i所需的步长，可以得到状态转移为：

—-》如果dp[j]包含了val、val-1、val+1，则dp[i].add(val)

这也是使用TreeSet的原因，由于需要找到dp[j]中[val-1, val+1]这个范围的值，使用floor(val+1)找到小于或等于val+1的最大的数，再判断是否大于等于val-1.

三、代码

  1. class Solution {
  2.     public boolean canCross(int[] stones) {
  3.         TreeSet[] dp = new TreeSet[stones.length];
  4.         for (int i = 0; i < dp.length; i++) {
  5.             dp[i] = new TreeSet<Integer>();
  6.         }
  7.         dp[0].add(0);
  8.         for (int i = 1; i < stones.length; i++) {
  9.             for (int j = i - 1; j >= 0; j--) {
  10.                 int stepNeed = stones[i] - stones[j];
  11.                 Integer findVal = (Integer)dp[j].floor(stepNeed + 1);
  12.                 if (findVal != null && findVal >= stepNeed - 1) {
  13.                     dp[i].add(stepNeed);
  14.                 }
  15.             }
  16.         }
  17.         return dp[dp.length - 1].size() > 0;
  18.     }
  19. }

时间复杂度为403. 青蛙过河-每日一题 - 图1，其中log(n)是TreeSet查找值的复杂度