DP - Introduction

Dynamic Programming (DP for short) is a fundamental technique in the development of efficient algorithms.

Mastering this technique will allow you to solve a lot of problem that seem intractable at first and is a necessary condition in order to be a successful algorithmist.

We will start by studying the Knapsack problem and use it to illustrate several aspects of DP, namely:

  • Top-down DP vs Bottom-up DP
  • The DP state graph
  • Reconstructing the solution
  • DP memory reduction
  • DP state reformulation

Mark this section as read?

Information

Author(s) François Aubry
Deadline No deadline
Submission limit No limitation

Sign in