Can this be solved using dp?

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

Автор jhjfbsbfkbjfnfnfjfj, история, 6 лет назад, По-английски

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.

jhjfbsbfkbjfnfnfjfj
6 лет назад
3

Комментарии (3)

Написать комментарий?

Ahmadsm2005

6 лет назад, скрыть # |

← Rev. 2 →

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.

→ Ответить

jhjfbsbfkbjfnfnfjfj

6 лет назад, скрыть # ^ |

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

}

→ Ответить