python - 原始计算器的动态规划

Question

我正在处理这个问题，这与零钱问题非常相似。

我需要实现一个简单的计算器，它可以对当前数字 x 执行以下三种运算:x 乘以 2、x 乘以 3 或 x 加 1。

目标是给定一个正整数n，从数字1开始求出得到数字n所需的最少操作次数。

我对此采用了贪婪的方法，但它显示的结果不正确

import sys

def optimal_sequence(n):
    sequence = []
    while n >= 1:
        sequence.append(n)
        if n % 3 == 0:
            n = n // 3
        elif n % 2 == 0:
            n = n // 2
        else:
            n = n - 1
    return reversed(sequence)

input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
    print(x)

例如:

Input: 10
Output: 
4
1 2 4 5 10

4 个步骤。但正确的步骤是 3 个步骤:

Output: 
3
1 3 9 10

我读到了动态规划，希望我能在这里实现它。但是，我不知道如何在特定情况下正确使用它，有人可以给我建议吗？

Answer 1

用一个简单的递归和Memoization就可以解决它:

代码:

d = {}

def f(n):
    if n == 1:
        return 1, -1
    if d.get(n) is not None:
        return d[n]
    ans = (f(n - 1)[0] + 1, n - 1)

    if n % 2 == 0:
        ret = f(n // 2)
        if ans[0] > ret[0]:
            ans = (ret[0] + 1, n // 2)

    if n % 3 == 0:
        ret = f(n // 3)
        if ans[0] > ret[0]:
            ans = (ret[0] + 1, n // 3)

    d[n] = ans
    return ans

def print_solution(n):
    if f(n)[1] != -1:
        print_solution(f(n)[1])
    print n,

def solve(n):
    print f(n)[0]
    print_solution(n)
    print ''

solve(10)

提示:f(x)返回一个元组(a, b)，其中a表示从1得到x的最少步数，b表示前面的数以获得最优解。 b 仅用于打印解决方案。

输出:

4 # solution for 10
1 3 9 10 

7 # solution for 111
1 2 4 12 36 37 111

您可以调试我的代码并了解它是如何工作的。如果你是 DP 的初学者，你可以阅读我的另一个 SO post关于 DP 以快速入门。

---

由于Python不能递归很多(10000左右)，我写了一个迭代版本:

# only modified function print_solution(n) and solve(n)

def print_solution(n):
    ans = []
    while f(n)[1] != -1:
        ans.append(n)
        n = f(n)[1]
    ans.append(1)
    ans.reverse()
    for x in ans:
        print x,

def solve(n):
    for i in range(1, n):
        f(i)[0]
    print_solution(n)
    print ''

solve(96234) # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234