dynamic_programming.md

Dynamic programming

Table of contents

• General information
• Linear partition
• Longest increasing subsequence

---

General information

🎥

• Dynamic programming. Part I, Part II, Part III, Part IV – MIT 6.006: Introduction to algorithms (2011)

📖

• Ch. 8: Dynamic programming – S.S.Skiena. The algorithm design manual (2008)

---

Linear partition

Problem: partition (without reordering) a set of non-negative integral numbers into k ranges such that the maximum sum over all the ranges is minimized.

📝

• This problem has another solution based on binary searching the answer in the space of possible answers that is obtained using a greedy approach.

📖

• Sec. 8.5: The partition problem – S.S.Skiena. The algorithm design manual (2008)
• Sec. 8.4.1: Two components: Binary search the answer and other – S.Halim, F.Halim. Competitive programming (2013)

---

Longest increasing subsequence

See Sequence algorithms – Longest increasing subsequence.