View difference between Paste ID: PLQ7bZ96 and JSQGQyUd

 有n层楼梯，每次可以爬1~2步，问能爬的最少的能整除 m 的步数是多少？ n <= 10000, m < 20.
 
 n 小于等于一万, 用 dfs + memo 会栈溢出.
 请问怎么把下边的  DFS + Memoization 转换成 DP 数组递推?
 
 class Solution:
     def minStep(self, n, m):
         if n < m:
-        # DFS + memoization,
+
         # DFS + memoization, 返回最小步数, 没有就返回正无穷, 记忆数组 f 唯一索引是 (n, steps)
         f = [[-1] * (n + 1) for _ in range(n + 1)]
         ans = self.dfs(n, m, 0, f)
         if ans == float("inf"):
             return -1
         return ans
 
     def dfs(self, n, m, steps, f):
         if n < 0:
             return float("inf")
         if n == 0:
             if steps % m == 0:
                 f[n][steps] = steps
                 return steps
             return float("inf")
         if f[n][steps] != -1:
             return f[n][steps]
         ans = float("inf")
         ans = min(ans, self.dfs(n - 1, m, steps + 1, f))
         ans = min(ans, self.dfs(n - 2, m, steps + 1, f))
         f[n][steps] = ans
         return ans
 
-n, m = 271, 5
+
-n, m = 10, 2
+n, m = 271, 8
 # n, m = 10, 2
 n, m = 1271, 7
-print(ans)
+
 ans = o.minStep(n, m)
 print(ans)
 
 动态规划思路，在所有能走到的n的步数当中，找到最小的能整出m的那一个步数。
 二维数组，第1维 n个台阶，第2维，走到n需要的步数。
 
 class Solution:
     def minStep(self, n, m):
         if n < m:
             return -1
 
         # DP, 分两步. 1. 找到能走到 n 的步数, 2. f[n] 数组里面, 从小到大找最小整除 m 的数字, 返回.
         f = [[False] * (n + 1) for _ in range(n + 1)]
         for i in range(n + 1):
             f[0][i] = True
         for i in range(1, n + 1):
             for j in range(1, i + 1):
                 if f[i - 1][j - 1]:
                     f[i][j] = True
                 if f[i - 2][j - 1]:
                     f[i][j] = True
         for i in range(n + 1):
             if f[n][i] and i % m == 0:
                 return i
         return -1