jhjfbsbfkbjfnfnfjfj's blog

Can this be solved using dp?
By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

I have been seeing a lot of questions like converting a number X to Y by following sets of operations.(add, subtract, multiply)Given a initial number x and two operations which are given below: Multiply number by 2. Add 1 to the number. i wonder if it can be solved using dp.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Yes, but greedy is a lot faster. You can build up a 2D DP tabulation. The i would be the difference between X and Y. The i is the number of operations as for the j, it is the Y. Total complexity will be:(O(Y*(Y-X))). Note that you don't have to continue building up as in most cases, you will find an answer early.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    thanks can you just tel if this approach is correct? int main() { int x, y; cin>>x>>y; int dp[1000]={0};

    for(int  i = x; i <= 100; i++){

                 if(!dp[2*i])       
         dp[2*i] = dp[i] + 1;
                   if(!dp[i+1])
         dp[i+1] = dp[i] + 1;

}

for(int i = x; i< 20; i++){
    cout<<i<<" "<<dp[i]<<endl;
}

    }

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yep! I see that it is correct. Your method also saves extra memory which is good!

      → Reply