eddycael's blog

Help about easier DP problems.

By eddycael, 9 years ago, In English

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...

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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;
   }
    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply