法1: 记忆化搜索
简而言之 就是把已经搜索的值记录到一个hash表 如果已经搜索过 那么就不用继续往下搜索了

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
MOD = 10 ** 9 + 7

class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        # hash 存储记忆化的中间结果
        memo = defaultdict(int)
        # 记忆化搜索
        # 当前距离为cur 已经走了d步 的方案数
        # 写python 记忆化搜索一定要加个@cache 不然就会超时
        @cache
        def dfs(cur: int, d: int) -> int:
			# 剪枝 剩余步数小于 终点起点之间的距离则方案肯定不行
            if k - d  < abs(endPos - cur):
                return 0
			if d == k:
                return 1
            # 这个key的赋值 是整个记忆化里最关键的一步
            # key包含cur 以及 d 两个信息
            # 如果只是从0开始 这两个信息可能会其冲突 比如 你cur = 3 可能只是向右了3步 但也可能是向右6步后折返了3步 即会产生哈希冲突
            # 由于题目条件是最多走1000步 所以只要cur* 比1000大的数 不同的key之间就不会存在冲突了 
            key = cur * 1005 + d
            # 已经搜索过直接返回
            if memo.get(key):
                return memo[key]
            v = (dfs(cur + 1, d + 1) + dfs(cur - 1, d + 1)) % MOD
            memo[key] = v
            return v

        return dfs(startPos, 0)

个人觉得记忆化写起来并没有dp方便 简洁性和正确性上来看 主要是记忆化需要判断较多的边界条件 能用dp的 还是尽量先考虑dp

法2:动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MOD = 10 ** 9 + 7


class Solution:
    def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
        if abs(endPos - startPos) > k:
            return 0

        # dp[i][j] 表示当前在坐标轴位置为i 已经了k步的方案数
        # 状态转移: 走了k步的状态 只能从走了k-1步的状态转移而来 而在数轴上又只可以左右移动
        # 即 dp[i][k] = dp[i-1][k-1] + dp[i+1][k-1]
        dp = [[0 for i in range(1010)] for _ in range(3010)]
        
        # 题目允许存在负数 所以+1000 避免负数的情况
        startPos = startPos + 1000
        endPos = endPos + 1000
        dp[startPos][0] = 1
        for j in range(1,k+1):
            for i in range(startPos - k,endPos + k+1):
                dp[i][j] = (dp[i-1][j-1] + dp[i+1][j-1]) % MOD
        
        return dp[endPos][k]