Introduction

• This framework is applicable to nearly every DP problem and provides a clear step-by-step approach to developing DP algorithms
• To solve a DP problem, we need to combine 3 things:
  • A function or data structure that will compute/contain the answer to the problem for every given state
  • A recurrence relation to transition between states
  • Base cases, so that our recurrence relation doesn't go on infinitely
• The number of state variables decides a dimension of a DP problem. However, the framework works regardless of the number of dimensions

You Will Know

• The Framework for DP
• Top-down to Bottom-up
• Representative Examples

Why Should You Learn These

Contents

Click cmd/ctrl + option/alt + T to expand all toggles

1. The Framework for DP

2. Top-down to Bottom-up

3. Climbing Stairs — Example

4. House Robber — Example

5. Pascal’s Triangle — Example

Conclusions

References

• link1

Further Readings

• a further reading for topic 1

Note