minStep_by_m

有n层楼梯，每次可以爬1~2步，问能爬的最少的能整除 m 的步数是多少？ n <= 10000, m < 20.

n 小于等于一万, 用 dfs + memo 会栈溢出.
请问怎么把下边的  DFS + Memoization 转换成 DP 数组递推?

class Solution:
    def minStep(self, n, m):
        if n < m:
            return -1
        # 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, 8
# n, m = 10, 2
n, m = 1271, 7
o = Solution()
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