【Leetcode每日一题】2021-04-29 403 青蛙过河 - 困难 - 动态规划 (Python & C++)

发表于 更新于 分类于 阅读次数：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

来源：力扣

为了选出新的首领，青蛙部落准备在河边举办一场比赛，部落的首领必须同时具备强健的体魄和灵活的头脑，所以举办方制定了如下的比赛规则：

  • 假定河流被等分为若干个单元格，在其中的一些单元格内放有一块石子。
  • 石子的位置存在stones中（用石子所在单元格的序号升序表示）。
  • 候选人只能从一块石子跳到另一块石子，跳入水中即视为淘汰。
  • 开始时，候选人站在第一块石子上，规定第一步只能跳一个单元格的距离，即只能从单元格1跳到单元格2，即stones[0]为0，stones[1]必须为1。
  • 为了选出最优秀的候选人，规定如果候选人上一步跳跃了k个单位，那么它接下来的跳跃距离只能为k-1、k或k+1个单位，而且只准向前跳（终点的方向）。
  • 胜利的条件就是跳到最后一块石子上（跳不到或者跳过头都视为淘汰）。


举办方为了比赛的公平和多样性，设计了很多不同的赛道stones，每个候选人都会从这些赛道中抽取自己的赛道，所以必须保证每条赛道都是有解的（即肯定有一种满足比赛规则的跳法能胜利），所以举办方请你来帮助验证赛道的有效性。

示例 1：
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：该赛道是有效的，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。

示例 2：
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。

提示：
2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0

标签：回溯，记忆化搜索，动态规划


1.记忆化搜索(DFS)

数据结构：set，map/dict
知识点：
  Python：
   - 用functools里的@lru_cache(None)及其语法糖@cache来实现记忆化搜索
   - set和dict的查找复杂度(a in set(b))都为$\mathcal{O}(1)$，而list查找复杂度为$\mathcal{O}(n)$，bisect查找复杂度为$\mathcal{O}(log(n))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        #将list转化为set以便于查找元素是否存在于stones
        stones_set = set(stones)

        # 实现记忆化搜索
        # @cache
        @functools.lru_cache(None)
        def dfs(pos, step):
            '''
            因为stones是升序的，所以不存在重复元素，
            (非降序则是存在重复元素)
            判断当前位置的值是否等于stones最后的值
            即可得出我们的蛙哥是否能跳到最后一块石头上
            '''
            if pos == stones[-1]: 
                return True

            # 遍历蛙哥下一步在k的基础上能跳的距离
            for d in [-1, 0, 1]:
                '''
                如果蛙哥下一步能跳到的位置刚好在stones里，
                那么就可以继续往下递归
                '''
                if step + d > 0 and \
                   pos + step + d in stones_set and \
                   dfs(pos + step + d, step + d):
                        return True
            return False

        return dfs(0, 0)

2. 动态规划

思路：
  首先要确定dp中的状态，这里我们将以石子为主体，将青蛙能否通过跳k个单位到该石子作为每个状态，所以dp是个二维数组，第一个维度自然是stones的长度，要确定第二个维度我们需要知道青蛙最多跳几个单位到达当前石子。因为青蛙第一次必然从stones[0]以一个单位跳到stones[1]，然后下一次最多跳1+1=2到stones[2]，以此类推，我们每次都能以最大距离跳到stones中的下一个石子，那么青蛙最多能跳i个单位到stones[i]，所以我们可以确定青蛙在整个过程中的跳跃距离不可能大于stones的长度n。所以dp第二个维度可以也设为n。
  然后要推出状态转移方程。以dp[i][k]为例，dp[i][k]代表青蛙从stones[j]跳k个单位到达stones[i]，有三种可能状态变为dp[i][k]，即dp[j][k+1]$\rightarrow$dp[i][k]，dp[j][k]$\rightarrow$dp[i][k]，dp[j][k-1]$\rightarrow$dp[i][k]，所以状态转移方程为:
   dp[i][k] = dp[j][k+1] or dp[j][k] or dp[j][k-1]

数据结构：list (Python), vector (C++)
知识点：
   - 这里的动态规划和常见的动态规划不同，当前的状态不是固定从前一个或几个状态转移而来，而是要遍历之前所有可能的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        n = len(stones)
        # dp[i][k]代表青蛙是否能通过跳k个单位到stones[i]
        dp = [[False]*n for _ in range(n)]
        # 初始条件青蛙已站在第一块石子上
        dp[0][0] = True

        for i in range(1, n):
            for j in range(i-1, -1, -1):
                # k为i和i之前石子j的距离
                k = stones[i] - stones[j]
                # 如果距离大于j+1，青蛙不可能跳得过来
                if k > j + 1:
                    break
                # 状态转移方程
                dp[i][k] = dp[j][k-1] or dp[j][k] or dp[j][k+1]
                # 只要存在一种方式能到达最后一块石子则返回True
                if i == n - 1 and dp[i][k]:
                    return True
        
        return False