This solution runs for 4ms in the OJ.

Consider the number `n`

as an array of bits `b[]`

. My idea is that we start from the highest bit `b[k]`

, which is always 1 (here `k = floor(log(n) / log(2))`

), to the lowest bit `b[0]`

. For every bit `b[i]`

, we consider the minimal steps we can achieve to reduce the bits `b[k] ... b[i]`

to `1`

. But this is not enough, because while processing the bits lower than `i`

, there can be `1`

carried from the add one operations.

So to include the carry condition, we define a function `d(i, j), i = 0...k, j =0,1`

, which means for the locations `i`

and the carry `j`

, the minimal steps we need to reduce the higher bits to 1. This is all the information we need to make a decision at position `i`

given `b[i]`

. So it satisify the condition of optimal substructures. We can design our dynamic programming algorithm thereon.

Next, we think about the state transition process. If `b[i] == 1`

and `j = 0`

, which means we suppose there is no carry produced from lower bits, we have two options: add `1`

to this bit and produce a carry, or minus `1`

to this bit and produce no carry. For the first option, the step we will take is `d(i+1, 1) + 2`

. The number `2`

comes from the two steps where we add `1`

to this bit and remove the resulting `0`

in the second step. For the second option, the number will be `d(i+1, 0) + 2`

, similarly. So the new function value should be `d(i, 0) = min(d(i+1, 0), d(i+1,1)) + 2`

. Using this logic, we can derive all the transition equations as follows.

```
if (b[i] == 1){
d[i][0] = Math.min(d[i + 1][0], d[i + 1][1]) + 2;
d[i][1] = d[i+1][1] + 1;
}else{ //b[i] == 0
d[i][0] = d[i+1][0] + 1;
d[i][1] = Math.min(d[i + 1][0], d[i + 1][1]) + 2
}
```

Since we are only using `d`

values from the `i+1`

step, we don't need a 2D array to store all the `d`

values; Instead, we use two variables `carry`

and `notCarry`

, for `d[i+1][1]`

and `d[i+1][0]`

, respectively. Additionally, we use the third variable `prevNotCarry`

to avoid overriding the previous `d`

values during updates. This leads to the following JAVA program.

```
public class Solution {
public int integerReplacement(int n) {
int log = 0;
for (int t = n; t > 0; t = t>>1) log++;
int carry = 1;
int notCarry = 0;
int prevNotCarry = 0;
for (int i = log - 2; i >= 0; --i){
int c = n & (1 << i);
if (c > 0){
notCarry = Math.min(prevNotCarry, carry) + 2;
carry = 1 + carry;
prevNotCarry = notCarry;
}else{
notCarry = prevNotCarry + 1;
carry = Math.min(prevNotCarry, carry) + 2;
prevNotCarry = notCarry;
}
}
return notCarry;
}
}
```