# Learning Dynamic Programming

Dynamic programming is a commonly-used method in a programmer’s algorithm toolbox and one that I have yet to learn. Thus I am writing this post to document what I learned in Stanford’s Design and Analysis of Algorithms.

Dynamic programming is based on the idea of solving a complex problem by breaking it down into many simpler subproblems, solving each of the subproblems just once and storing the solution. When the same subproblem occurs again, the solution can be simply looked up from storage, thus saves time at the expense of space.

## Principles of Dynamic Programming

1. Identify a small number of subproblems
2. Quickly and correctly solve “larger” subproblems, given the solutions to smaller subproblems
3. After solving all subproblems, the final solution can be quickly computed

## Example Problem 1: Weighted Independent Sets in Path Graphs

### Problem Statement

Path graphs are basically graphs like a linked list. The input for the Weighted Independent Sets (WIS) problem is a path graph with non-negative weights on the vertices. And the desired output would be the subset of non-adjacent vertices, also called independent set, with maximum total weight.

### Subproblem

Let $S$ be the max-weight independent set of the path graph $G$ and $V_n$ to be the last vertex of the path. Let $G'$ be the path graph $G$ with $V_n$ deleted

• Case 1: If $V_n \notin S$, then $S$ is also the max-weight IS of $G'$.