一个动态算法的问题超时

Question

我正在处理一个算法问题： https://leetcode.com/problems/integer-replacement/

Given a positive integer n, you can apply one of the following operations:

    If n is even, replace n with n / 2.
    If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

我决定使用迭代动态规划方法，因此我创建了一个字典来跟踪所有重叠子问题的最佳解决方案。这是我的代码：

class Solution:
    def integerReplacement(self, n: int) -> int:
        
        dic = {1:0}
        
        for i in range(2, n+1):
            #print(i)
            if i % 2 == 0:
                dic[i] = dic[i/2]+1
            else:
                dic[i] = min((dic[(i+1)/2]),(dic[(i-1)/2]))+2
            #print(f"dic[{i}] is {dic[i]}")
                
        return dic[n]

我通过了 19 个案例，但在输入 100000000 次时超时（其中 1 次它说使用了太多 space）。

所以，我的问题是：我的动态编程实现是否有缺陷，或者在这种情况下它根本不是可行的方法？

谢谢

Answer 1

这个问题可以用 O(log(n)) 时间复杂度和 O(1) space 复杂度来解决。

这就是他们提供大量投入的原因。因此，您的代码不是最佳选择。

现在，如何解决：

1. 如果 n 为偶数则除以 2.

2.如果n是奇数：

(a) 如果 (n-1)//2 的结果可以被 2 整除，那么这是最优的。但是对于一个边缘情况，即 3 那么你必须选择 (n-1) 操作，因为除法之后你可以达到你的目标，即 1.

(b) else n+1 操作因为 (n+1)//2 会得到一个可以被 2 整除的数.

这是将通过所有测试用例的代码：

class Solution:
    def integerReplacement(self, n: int) -> int:
        
        operation = 0
        while(n > 1):
            operation = operation + 1
            if(n%2 == 1):
                if( ((n-1)//2)%2 == 0 or (n-1)//2 == 1):
                    n = n - 1
                else:
                    n = n + 1
            else:
                n = n//2
        
        return operation

一个动态算法的问题超时

Time out on a problem with a dynamic algorithm

python

algorithm

dynamic-programming