403.青蛙过河

链接：403.青蛙过河
难度：Hard
标签：数组、动态规划
简介：一只青蛙想要过河。

题解 1 - typescript

• 编辑时间：2021-04-29
• 执行用时：948ms
• 内存消耗：44.5MB
• 编程语言：typescript
• 解法介绍：动态规划，记录每个石头可跳的步数。

function canCross(stones: number[]): boolean {
  const len = stones.length;
  const dp: Set<number>[] = new Array(len).fill(0).map(_ => new Set<number>());
  dp[0].add(0);
  for (let i = 1; i < len; i++) {
    const stone = stones[i];
    for (let j = 0; j < i; j++) {
      const minus = stone - stones[j];
      const set = dp[j];
      if (set.size === 0) continue;
      if (set.has(minus) || set.has(minus - 1) || set.has(minus + 1)) {
        dp[i].add(minus);
      }
    }
  }
  return dp[len - 1].size !== 0;
}