# DP

1. **When to use dynamic programming?**
   1. If we can break the problem into subproblems such that
      1. the original problem can be solved relatively easily once solutions to the subproblems are available
      2. we solve some subproblems repeatedly
      3. we can cache the solution to subproblems
   2. The question usually asks for maximum or minimum.
2. **Top-down or bottom-up**
   1. top-down:
      1. The question we should ask is: what if the first element is used, what if it's not used?
      2. Usually we can visualize the solution in a tree from top to bottom.
      3. Recursion is often used.
      4. If it's a dynamic programming problem, we can cache the solutions along the way.
      5. Very similar to backtracking solutions. The difference is in backtracking problems, we have to traverse the whole tree to return all the output. But in dynamic programming, we don't need to return all the path. Usually we are updating something along the way.
   2. bottom-up:
      1. The question we should ask is: if we have the solution to the subproblem A\[0:n-2], how can we find solution for adding one more element A\[n-1]?
      2. We won't traverse the tree, instead there will be linear search.
      3. Iteration is often used.
      4. One advantage of bottom-up is that when processing some paths will be pruned early.
      5. In a dynamic programming problem, try to come up a bottom-up solution first because bottom-up costs less space.
3. **Two typical ways when cache  results**
   1. cache a constant number of results. 
      1. In bottom-up solution, when we add element A\[n-1] , the information we need from solution to the subproblem A\[0:n-2] is up to constant.
      2. Example: 53\_Maximum Subarray
   2. cache in a array of the same length as the input
      1. In bottom-up solution, when we add element A\[n-1] , the information we need from solution to the subproblem A\[0:n-2] is related with each element.
      2. Example: 300\_ Longest Increasing Subsequence


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/dynamic-programming.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.