Блог пользователя jhjfbsbfkbjfnfnfjfj

Can this be solved using dp?
Автор jhjfbsbfkbjfnfnfjfj, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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;
}

    }

    → Ответить