CPSIG Week 2: Dynamic Programming.

Dynamic Programming (DP) is more of a technique than a topic. Your skill in solving DP problems will increase with more and more practice of different types of DP problems. Here i try to mention a list of topics, learning resources and practice problems which should give you a good foundation.  

Learning Material

Basic Track:

Longest Common Subsequence

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Longest Increasing Subsequence
In O(n^2) - http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/ (See the second implementation)
In O(n*logn) - http://comeoncodeon.wordpress.com/2009/08/12/longest-increasing-subsequence-lis/

Edit Distance
http://en.wikipedia.org/wiki/Levenshtein_distance

Read the Iterative with full matrix solution first.

Matrix Chain Multiplication
http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/

0/1 Knapsack
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm

Some more Classical DP Problems: http://people.csail.mit.edu/bdean/6.046/dp/

Solving DP using Matrix Exponentiation

If DP problem can be reduced to a recurrence relation, then use matrix exponentiation to solve the problem.

Solving DP using Bitmasking

Usually these are problems where all possible subsets need to be generated and we need to store information about each subset to avoid re-computation.

Advanced Track:

Reading:
Commonly used DP State Domains - http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0


Topics and practice problems:

State Space Reduction
http://www.topcoder.com/stat?c=problem_statement&pm=8605&rd=12012&rm=269199&cr=7581406

Counting

Strategies and Expected values

Solving in reverse - Easier characterization from the end.
http://www.spoj.pl/problems/MUSKET/

DP on Trees

DP with Data Structures

Practice Problems

Basic Track:
AIBOHP, AMZSEQ, KNAPSACK, SAMER08D, ELIS, LIS2, M3TILE, GNY07H, HIST2, MIXTURES, SCUBADIV, DCEPCA06, DCEPC501, EDIST, ACODE

Advanced Track: 
MUSKET, COURIER (more to be updated here...)

Some more problems:
http://codeforces.com/blog/entry/325

http://apps.topcoder.com/forums/;jsessionid=B83B4A412C257FA7F334AD9649D3E766?module=Thread&threadID=674592&start=0&mc=9#1775726