求助一道算法题, 在限定三个operation下使一个数变成1的最小操作数# JobHunting - 待字闺中
d*n
1 楼
The description of the problem is : Write a function which takes a positive
integer as a string and returns the minimum number of operations needed to
transform the number to 1. The number is up to 309 digits long, so there won
't too many character than you can express in that many digits. The
transform process is limited to three operations: 1. Add 1 2. Subtract 1 3.
Divide the number by 2 (only even number allow here)
我的想法是用dfstraverse所有可能, 用memorization来剪枝,但是最后还是超时了,
求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦
integer as a string and returns the minimum number of operations needed to
transform the number to 1. The number is up to 309 digits long, so there won
't too many character than you can express in that many digits. The
transform process is limited to three operations: 1. Add 1 2. Subtract 1 3.
Divide the number by 2 (only even number allow here)
我的想法是用dfstraverse所有可能, 用memorization来剪枝,但是最后还是超时了,
求教如何进一步优化或者一种方法处理。 因为输入时string所以处理起来很麻烦