Boohoo ~ It’s dp time

1. Introduction to Dynamic Programming

Dynamic programming (abbreviated DP), is an approach to solving problems through ‘clever bruteforce’. It is a technique that combines the correctness of complete search and the efficiency of greedy algorithms. Dynamic programming can be applied if the problem can be divided into overlapping subproblems that can be solved independently.

There are two common uses for dynamic programming:

• Finding an optimal solution: You want to find a solution that is as large as possible or as small as possible.
• Counting the number of solutions: You want to calculate the total number of possible solutions.

If you’re following this series, DP could be quite a jump in terms of difficulty and thinking of approaches to problems. Take your time to assimilate the contents of the following links/guides and understand what’s going on. The internet has a lot more resources to explore if you’re stuck.

The links that follow are good to start with, but you will most probably have to revisit and re-read them multiple times as you struggle through the components that follow.

Reading material:

• Errichto DP Lecture #1 [V]
• Topcoder [B]
• Hackerearth [B]
• Blog [B]

Note: Solutions to AtCoder DP contest problems can be found here.

2. Coin change

Reading material:

• Errichto DP Lecture #2 [V]
• CPH Ch 7, pg 65 - 70
• Blog [B]

Note: Solutions to CSES DP section problems can be found here.

3. Maximum sum subarray (Kadane’s algorithm)

Reading material:

• Medium [B]
• CPH Ch 2, pg 21 - 23

4. Knapsack

Reading material:

• Algorithms Live [V]
• CPH Ch 7, pg 72 - 73
• HackerEarth

5. Longest Common Subsequence & Edit distance

Reading material:

• Longest Common Subsequence
  • Blog [B]
  • Errichto [V]
• Edit distance
  • Blog [B]
  • CPH Ch 7, pg 74

6. Longest Increasing Subsequence

The dp approach is $\mathcal{O}(n^2)$ and helps build intuition and understanding. However, since there exists methods to solve it in O(nlogn), often you will not be able to use this approach.

Reading material:

• $\mathcal{O}(n^2)$
  • CPH Ch 7, pg 70
• $\mathcal{O}(nlogn)$
  • USACO guide
  • CP Algorithms

7. Grid DP

Reading material:

• Hackerearth [B]
• CPH Ch 7, pg 71 - 72
• Errichto [V]

8. Matrix Chain Multiplication style DP

Reading material:

• Introduction to Algorithms, CLRS pg 370
• Blog [B]
• Video [V]

Practice

Recommended:

• CSES DP section

  Editorial

  My solutions

• AtCoder DP contest

  Errichto solutions [V]

Some easy problems

• Codeforces 180 C
• Codeforces 456 C
• Codeforces 166 E
• Codeforces 698 A
• Codeforces 1196 D1
• Codeforces 1196 D2
• Codeforces 607 A
• Codeforces 106 C

Knapsack

• Spoj KNAPSACK
• Spoj SCUBADIV
• Hackerearth Bob and K-Subset
• Codeforces 35 D

Segments and subsequences

• Spoj AIBOHP
• Spoj SAMER08D
• Spoj MIXTURES
• Codeforces 1061 C
• Codeforces 977 F
• Codeforces 983 B
• Codeforces 1183 H

Combinatorics and number theory

• Codeforces 533 A
• Codeforces 1081 C
• Codeforces 166 E
• Codeforces 546 D
• Codeforces 474 D
• Codeforces 182 E

Misc.

• Codeforces 1015 E1
• Codeforces 1051 D
• Codeforces 577 B

If you’re following the series, the motivation here is to make yourself familiar with the topics mentioned above. You may find some of these problems fairly difficult, so the idea is to put those problems on hold but surely come back later to solve them. For now, try to attempt at least the first two problems of each sub topic.

Competitive Programming Beginner Topics Part 5