# “将数字转换为1的最小操作次数”

go评论44阅读模式

Minimum operations to convert number to 1

# 问题

• 减去 1
• 除以 2（最多 K 次）

``````private int getMinRounds(int N, int K, int memo[])
{
if(N <= 1) return 0;
if (memo[N] != -1) return memo[N];

int rounds;
if ((N%2) == 0 && K > 0) {
rounds = 1 + Math.min(getMinRounds(N-1, K, memo), getMinRounds(N/2, K-1, memo));
}else {
rounds = 1 + getMinRounds(N-1, K, memo);
}
memo[N] = rounds;
return rounds;
}

private int solution(int N, int K)
{
int memo[] = new int[N + 1];
Arrays.fill(memo, -1);
return getMinRounds(N, K, memo);
}
``````

Given a number N and number K, find minimum number of operations to convert N to 1.
allowed operations:

• subtract 1
• divide by 2 (at most K times)

here is my code but it is not working correctly.

``````  private int getMinRounds(int N, int K, int memo[])
{
if(N &lt;= 1) return 0;
if (memo[N] != -1) return memo[N];

int rounds;
if ((N%2) == 0 &amp;&amp; K &gt; 0) {
rounds = 1 + Math.min(getMinRounds(N-1, K, memo), getMinRounds(N/2, K-1, memo));
}else {
rounds = 1 + getMinRounds(N-1, K, memo);
}
memo[N] = rounds;
return rounds;
}

private int solution(int N, int K)
{
int memo[] = new int[N + 1];
Arrays.fill(memo, -1);
return getMinRounds(N, K, memo);
}
``````

# 答案1

``````int solve(int n, int k) {
if (n == 1) return 0;
if (k == 0) return n - 1;
if (n % 2 == 0) return 1 + solve(n / 2, k - 1);
return 1 + solve(n - 1, k);
}
``````

``````solve(1, 1) = 0
solve(2, 2) = 1
solve(3, 3) = 2
solve(4, 0) = 3
solve(5, 1) = 3
solve(6, 2) = 3
solve(7, 3) = 4
solve(8, 0) = 7
solve(9, 1) = 5
solve(10, 2) = 4
``````

A greedy aproach should be enough to solve this problem. The bigger the number is, the best it is to divide it by 2 already, so you don't need to think "is it better to divide now or store the division for later?". The bigger the number you can divide is, the best for you it will be to divide it.

``````int solve (int n, int k){
if(n == 1) return 0;
if(k == 0) return n - 1;
if(n % 2 == 0) return 1 + solve(n / 2, k - 1);
return 1 + solve(n - 1, k);
}
``````

Complexity: O(log(n))

OUTPUTS solve(n, k)

``````solve(1, 1) = 0
solve(2, 2) = 1
solve(3, 3) = 2
solve(4, 0) = 3
solve(5, 1) = 3
solve(6, 2) = 3
solve(7, 3) = 4
solve(8, 0) = 7
solve(9, 1) = 5
solve(10, 2) = 4
``````

• 本文由 发表于 2020年7月30日 07:35:02
• 转载请务必保留本文链接：https://go.coder-hub.com/63164012.html
• algorithm
• java

go 37

go 33

go 42

go 35