algorithm - Multiply/add initial number to get target number -

suppose have target number n e.g. 5, , start number 1 , have *2 or *3 or +1 until reach n. in case *2 twice, +1 5.

i supposed find least number of operations reach target value. see similar question being posted requires fixed number of steps while have figure out least steps. there tips on how can tackle problem?

this homework problem.

it can regarded search or dp problem (yes in essence both related state transition), key point define search state condition, suppose n positive, here define f[i] = inf, inf large integer means number i not reachable, f[i] = k, k >= 0 means number i can reached in @ least k steps.

if n not large, can use array store least steps each number 1 n. initial f[1] = 0 , f[i] = inf, 2 <= <= n. if need output how target(ex, output of 5 1 2 4 5), can use array pre store operations, define pre[i] = j means number i produced number j(ex, pre[4] = 2 means number 4 produced number 2, because 2*2=4; pre[3] = 1 means number 3 produced number 1, because 1*3=3):

    int inf = integer.max_value;     f[1] = 0;     pre[1] = -1; // pre[i] = -1 means start point     for(i=2;i<=n;i++) {         f[i] = inf;         pre[i] = -1;     }      for(int i=1;i<=n;i++) { // since each number positive smaller number cannot produced via larger number, no need consider > n issue         if(f[i] == inf) {             continue;         }         if(2*i <= n && f[i] + 1 < f[2*i]) {             f[2*i] = f[i] + 1;             pre[2*i] = i; // means number 2*i produced number         }         if(3*i <= n && f[i] + 1 < f[3*i]) {             f[3*i] = f[i] + 1;             pre[3*i] = i;         }         if(i+1 <= n && f[i] + 1 < f[i+1]) {             f[i+1] = f[i] + 1;             pre[i+1] = i;         }     } 

the answer f[n].

how output how target, use pre array recover operations:

        curr = n;         pos = 0;         ans[pos] = n;         while(pre[curr] != -1) {             pos++;             ans[pos] = pre[curr];             curr = pre[curr];         }         for(int i=pos;i>=0;i--) { // reverse order output             system.out.println(ans[i]);         } 

while if n large, may need use priority queue maintain state transition , hash set maintain least steps each number.