使用动态算法解决问题超时

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个输入时超时(有一次它说使用了太多空间(。

所以，我的问题是：我的动态编程实现是有缺陷的，还是在这种情况下根本不是这样？

谢谢

Answer 1

这个问题可以在O(log(n((时间复杂度和O(1(空间复杂度下解决

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

现在，如何解决它：

1。如果n是偶数，则将其除以2。

2.如果n是奇数：

(a(如果(n-1(//2产生一个可被2整除的数，则这是最优的。但是对于一个边的情况，即3，那么你必须选择(n-1(运算，因为除法之后你可以达到你的目标，即1。

(b(其他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