One Pager Cheat Sheet

• This lesson will help you demystify and learn the skill of Dynamic Programming by walking through examples and providing a system to help solve most problems.
• Dynamic Programming helps us save time by remembering information.
• Using the FAST method can help us break down complex problems into smaller subproblems, such as calculating the nth Fibonacci number.
• The Fibonacci sequence is a recursive formula where each number is the sum of the previous 2 numbers.
• We need to find the brute force solution for the nth Fibonacci number as the first step of the FAST method before we can optimize it.
• Our solution uses Dynamic Programming because it has both overlapping subproblems and an optimal substructure.
• We identify the subproblems as fib(n-1) and fib(n-2) in order to memoize them and save results.
• We are creating a cache to store already computed solutions and returning them if they exist, leading to a time complexity of O(n) and a space complexity of O(n).
• We will iteratively build from the base case and work our way up to solve the problem.
• The bottom-up solution has an O(n) time and space complexity, while being easier to understand and more intuitive than the top-down solution.
• Dynamic programming is an algorithm that solves complex problems by breaking them down into smaller subproblems and combining the solutions to obtain the optimal results, and it can be done either via a top-down or bottom-up approach.
• The FAST method of dynamic programming trades off the time complexity of the algorithm for increased space complexity by allocating additional space to store data, thereby reducing the amount of time required to solve the problem.
• By using a bottom-up approach to consider how much money can be made robbing 0 to n houses, the House Robber problem can be solved to find the maximum amount of money that robbers can make.
• We would rob only one house and take what it has.
• If house A has more money, we rob house A; otherwise, we rob house B.
• The bottom-up (iterative) process of dynamic programming can be utilized to solve for the nth answer by solving smaller subproblems for the ith answer.
• The code put together would look like this.
• The bottom-up approach of solving simpler cases and building an array arr to store the max amount of money we can rob up to and including the current house ultimately allows us to find the maximum amount of money that can be robbed.
• Dynamic programming allows for problems to be broken down into smaller subproblems and solutions from these subproblems to be stored and used to solve the larger problem, allowing for solutions without the need for knowledge of previous and current states, such as calculating the maximum amount of money we can rob for each house.
• With FAST and enough practice, Dynamic Programming can be used to reach an optimal solution.
• Using dynamic programming, the problem can be solved by initializing an array, looping from 0 to n, adding the base case, and filling the array using the recursive formula.