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...
Take a look at Timus online judge. You can filter the problems by DP tag and sort them by difficulty — link
Have fun :)
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'.
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
Thank you very much... I solved Longest Common Subsequence UVA 10405,Max 1D Range Sum UVA 10684, Edit distance SPOJ 6219, Coin Change UVA 674.
I try to learn about LIS, but I can't understand how works the solution O(N log N)... I visited pages but, I can't learn... Can you help me? (Sorry for my poor english.. my language is spanish)
Have you tried this page? http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming
try wiki for LIS O(NlogN)
I actually prefer the page I linked over wikipedia.
in ur link solution cant solve this problem , but segment tree on dynamic array can solve
Here's a list of DP problems on CF, in increasing order of difficulty.
where is the list?
Wow, I forgot. Lol.
http://codeforces.me/problemset/tags/dp?order=BY_SOLVED_DESC