Find the minimum length of expression that can be expressed as the exponential of binary number

https://discuss.leetcode.com/topic/123/find-the-minimum-length-of-expression-that-can-be-expressed-as-the-exponential-of-binary-number
Find the minimum length of expression that can be expressed as the exponential of binary number
e.g: input = 28
28 = 2^4 + 2^3 + 2^2 => num = 3
28 = 2^5 - 2^2 => num = 2
So output should be 2

Scan the binary representation of the number from the right to left and find the position of least significant 1. recursively call num+1(minus) or num-1(plus). Here is my code

public static int getMin(int n){
        if(n<=0) return 0;
        if(n==1) return 1;
        if((n & 1)==1) return 1 + Math.min(getMin(n+1),getMin(n-1));
        else return getMin(n>>1);
    }

you can think of it like a greedy algorithm. You start searching from the lease significant bit.. Because you only have two operation: either add or minus, so the result must come from one of them. As for the running time, if there is only 32 bit, the running time should be 0(1)

Addition of 1 is clear for me . For example if we have some number 0001111 and you add one you will decrease number of powers with 4 , because 0001111 + 1 = 0010000, but it is not still clear for me why substraction of 1 works, how solution is improved with subtraction.

There is a lot of recurrence though, we can use a hash map to store getMin(n+1) and getMin(n-1)

unordered_map<int, int> dp;

int getmin(int n)
{
    cout<<n<<endl;
    if(n<=0) return 0;
    if(n==1) return 1;
    if(n&1){
        if(dp.find(n+1)==dp.end()) dp[n+1]=getmin(n+1);
        if(dp.find(n-1)==dp.end()) dp[n-1]=getmin(n-1);
        return 1+min(dp[n+1],dp[n-1]);
    }
    else
    {
        if(dp.find(n>>1)==dp.end()) dp[n>>1]=getmin(n>>1);
        return dp[n>>1];
    }
}