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

Help about easier DP problems.

Автор eddycael, 10 лет назад, По-английски

I would like to have help learning Dynamic Programming, since the subject is unknown at my university, but I like to solve programming problems in online judges, and I would like to continue learning.

I have read about DP on sites like TopCoder. After think a lot I could solve the knapsack problem 0-1, the problem of coins, and others ... anyone know of similar problems? to begin improving in DP. Sorry for my poor English. Thanks in advance...

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Take a look at Timus online judge. You can filter the problems by DP tag and sort them by difficulty — link
Have fun :)

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

    Thanks for your link. I solved the problem Flags with DP in a recursive function. Could you help me to transform it a iterative DP? The idea is put the stripes with the rules, with the last 'u' and the previous to the last'pu'. 

    #include<bits/stdc++.h>
using namespace std;
#define For(i,a,n) for(int i=a;i<n;i++)
#define Fore(i,a,n) for(int i=a;i<=n;i++)
#define blanco 0
#define azul 1
#define rojo 2
int n;
unsigned int dp[46][3][3];
unsigned int maneras(int cant,int pu,int u)
   {
   if(dp[cant][pu][u]!=-1) return dp[cant][pu][u];
   if(u==azul)
      {
      if(cant==n) return dp[cant][pu][u]=0; // not at end
      if(pu==blanco)
         return dp[cant][pu][u]=maneras(cant+1,u,rojo);
      return dp[cant][pu][u]=maneras(cant+1,u,blanco);
      }
   if(cant==n) return dp[cant][pu][u]=1;
   unsigned int ans=0;
   For(cur,0,3)
      if(cur!=u)
         ans+=maneras(cant+1,u,cur);
   return dp[cant][pu][u]=ans;
   }
int main()
   {

   while(cin>>n)
      {
      For(i,0,46) For(I,0,3) For(J,0,3)
         dp[i][I][J]=-1;
      cout<<maneras(1,-1,rojo)+maneras(1,-1,blanco)<<endl;
      }
   return 0;
   }
    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I recommend to you First you have to solve some clasical dp problems , then after solve this problems you can have a general idea for solve a dp problem.

Longest Common Subsequence UVA 10405

Max 1D Range Sum UVA 10684

Edit distance SPOJ 6219

Coin Change UVA 674

Subset Sum UVA 562

Table additive 2D RECTQUER Codechef

Table additive 3D CUBE Codechef

Longest Increasing Subsequence UVA 111

Then if you can solve this problems easily you can try some problems not so classics. There are a lot of solvable problems with DP for example UVA have a list of dp problems and also many other online judges

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here's a list of DP problems on CF, in increasing order of difficulty.

→ Ответить