Why does DP solve a problem in polynomial time whereas brute force is exponential?

Question

I am just learning DP, so maybe this is a noob doubt. I've read (while trying to understand the difference between DP and greedy approach - and I am still not fully clear) that DP goes through all possible solutions to a problem and chooses an optimal one. That's what brute force does right? Then why such a big difference in the running time? From whatever reads and re-reads I've given to various sources, I understand that probably it's got something to do with this thing called Principle of Optimality (I've already asked a question on it, but it was too broad, so it's closed down). But it'd be nice if someone could provide a more intuitive understanding of all this.

Answer 1

Dynamic programming is sort of an "elegant" brute force. While you are right in that most dynamic programming solutions involve producing all "smaller" solutions, the key difference is that these "smaller" solutions are tractable. Typically you will characterize a dynamic program with a recurrence relation, and if it is a good one, then you won't need all previous subproblems, just the most recent batch of them. Hence, you can start building up your solutions from the base case. Your struggles are natural: dynamic programming hurts sometimes. In my opinion, it is a strong testament to our limited intelligence. The solution is "try everything", but we are at least smart enough to do so in an efficient manner.

Here is an example of a dynamic programming solution from an old homework assignment from my algorithms class:

---

Problem: Say you're at an airport and you find yourself in a really long hall with two sets of $n$ walkways in parallel, and that each walkway has some time to traverse. Furthermore, switching sides takes a constant amount of time, say $k$. You want to find the fastest way to get across the hallway.

More formally, given two lists of length $n$ of walkway times for the right and left sides, and a time cost $k$ for switching between sides, a schedule is a sequence of length $n$ of the form {$L$, $R$}$^n$ , where an $L$ in position $i$ represents taking the left walkway for that segment, while an $R$ represents taking the right walkway. The cost of a schedule is the sum of the times for the walkways taken, plus $k$ times the number of switches between walkways. Give an efficient algorithm to calculate the fastest possible travel time to the gate.

Solution: Let $T_{R} = \{r_1, ..., r_n\}$ and $T_{L} = \{l_1, ..., l_n\}$ be the lists of walkway times for the right and left sides. Define $OPT(j)$ to be the fastest possible travel time to the $j^{th}$ pair of walkways. The purpose of our algorithm is to compute $OPT(n)$. The recursion uses the fact that the optimal schedule will either finish at the left or the right hand side. So, we will define two auxiliary functions $OPT_R(j)$ and $OPT_L(j)$, where \begin{align*} OPT_R(j) = \left \{ \begin{array}{lr} r_1 & j = 1\\ \text{min}\{OPT_R(j-1) + r_j, OPT_L(j-1) + k + r_j\} & 1 < j \le n \end{array} \right. \\OPT_L(j) = \left \{ \begin{array}{lr} l_1 & j = 1\\ \text{min}\{OPT_L(j-1) + l_j, OPT_R(j-1) + k + l_j\} & 1 < j \le n \end{array} \right. \end{align*} If it is not already clear, $OPT_R(j)$ and $OPT_L(j)$ functions whose output are the fastest times out of all the schedules that arrive at the $j^{th}$ right and left walkways, respectively Keeping in mind our main objective, we also define \begin{align*} OPT(j) = \text{min}\{OPT_R(j), OPT_L(j)\} \end{align*} To maximize efficiency, we should start at $j=1$ and work our way up to $j=n$. Each recursive call is only computationally dependent on the preceding pair of values, so we can calculate the fastest possible travel time with constant space (just the previous pair) and linear time ($n$ iterations, and one comparison per $OPT_L$ and one per $OPT_R$, excluding the base cases).

---

Notice that there are $2^n$ possible routes we could take (think binary strings), but thanks to our recursion, we can solve the problem in linear time and constant space. Hope this helps!

Answer 2

Dynamic programming differs from brute force mainly in that it keeps track of intermediate results.

For instance, suppose I wanted to compute the shortest path in a graph from $A$ to $B$. I could try each path in sequence, and sum of the length of the edges along the entire path. That's the naive, brute-force method.

Instead, I'll be smart, and compute the paths from $A$ to intermediate nodes $C,D,...$. Then, compute the shortest path from the intermediate nodes to B, and pick the shortest one. I've saved trying each path individually because many paths have overlapping subpaths (the whole point of Dynamic Programming is overlapping subproblems).

To contrast this with the greedy algorithm - for the greedy algorithm, at each step in the path, I would head to the node that is the shortest distance away from my current node. Its easy to see that this may not even generate a valid solution (it could get stuck in a loop), and if it DID generate a valid solution, it probably wouldn't be the longest. Would you rather walk 1 step 10 times, or 5 steps 1 time?