{"lesson":{"id":59,"title":"How Does DP Work? Dynamic Programming Tutorial","slug":"how-does-dp-work-dynamic-programming-explained","created_at":"2019-06-04T03:15:42.825Z","updated_at":"2023-09-20T23:45:31.594Z","image_url":"https://storage.googleapis.com/algodailyrandomassets/tutorials-optimized/Algorithms-F6CallTreeMemoized.png","section_id":22,"sequence":1,"locked":false,"video":null,"reading_time":"44","published":true,"newsletter_sequence":41,"video_thumbnail":null,"video_duration":null,"excerpt":"\n\n\u003cdiv class=\"objective-container bg-light mb-4 p-4 border\"\u003e\r\n\r\n**Objective**: In this lesson, we'll cover this concept, and focus on these outcomes:\r\n\r\n- You'll learn what `dynamic programming` is.\r\n- We'll demystify it by showing you how to use this concept in programming interviews.\r\n- We'll walk through several examples applying the technique.\r\n"},"completed":null,"screens":[{"id":1294,"kind":"info screen","options":[],"content":"\u003cdiv class=\"objective-container bg-light mb-4 p-4 border\"\u003e\r\n\r\n**Objective**: In this lesson, we'll cover this concept, and focus on these outcomes:\r\n\r\n- You'll learn what `dynamic programming` is.\r\n- We'll demystify it by showing you how to use this concept in programming interviews.\r\n- We'll walk through several examples applying the technique.\r\n\r\n\u003c/div\u003e\r\n\r\nOut of all the possible interview topics out there, `Dynamic Programming` seems to strike the most fear in people's hearts. `Dynamic Programming` is somewhat unintuitive and there's an aura around it as something to be feared.\r\n\r\nBut there's no reason why it should be this way! Taking the time to properly understand these problems can make `Dynamic Programming` (`DP`) fun and easier to understand. Throughout this lesson, we'll cover a system to help solve most of these problems and to show that all dynamic programming problems are very similar.\r\n\r\n\u003cimg src=\"https://upload.wikimedia.org/wikipedia/commons/a/a4/Algorithms-F6CallTreeMemoized.png\" class=\"img-fluid\" /\u003e","code":"0","full_screen":true,"solution":"0","lesson_id":59,"challenge_id":null,"sequence":1,"title":"Introduction","slug":"introduction","created_at":"2020-06-04T14:03:39.505Z","updated_at":"2023-01-07T06:03:44.089Z","explanation":null,"summary":"\nThis 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."},{"id":1295,"kind":"info screen","options":[],"content":"## Deep Dive into Dynamic Programming\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/intro-to-dynamic-programming/DyProg1.png\" class=\"img-fluid\" /\u003e\n\nIf I were to ask you what the sum of these numbers are, you know the answer would be `6`.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/intro-to-dynamic-programming/DyProg2.png\" class=\"img-fluid\" /\u003e\n\nBut let's say if I were to say add another `1` to the right of these digits. Then you'd also know what the answer is `7`. \n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/intro-to-dynamic-programming/DyProg_2.png\" class=\"img-fluid\" /\u003e\n\nThis may seem elementary. But the reason you didn't need to recount was that you remembered there were `6`. This is the foundation of `Dynamic Programming`, **remembering information to save time**.","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":2,"title":"Deep Dive Into Dynamic Programming","slug":"deep-dive-into-dynamic-programming-2","created_at":"2020-06-04T14:03:39.679Z","updated_at":"2023-01-07T06:03:45.635Z","explanation":null,"summary":"\n`Dynamic Programming` helps us save time by **remembering information**."},{"id":1296,"kind":"info screen","options":[],"content":"## The Theory\n\nDynamic Programming is a method for solving a complex problem by breaking it down into a collection of simpler `subproblems`. These `subproblems` are solved just once and their solutions are stored using a memory-based `data structure` (via an array, hashmap, list, etc).\n\nThe solutions of a subproblem are typically stored and indexed in a specific way based on the values of its input parameters. This helps to facilitate its lookup.\n\nWhat that means is that the next time the same `subproblem` occurs, instead of _recomputing its solution_, you simply just lookup the previously computed solution which saves computation time. This process of saving the solutions to the subproblems instead of recomputing them is called `memoization`.","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":3,"title":"The Theory","slug":"the-theory-3","created_at":"2020-06-04T14:03:39.785Z","updated_at":"2020-06-17T01:34:05.417Z","explanation":null,"summary":null},{"id":1297,"kind":"info screen","options":[],"content":"### Solving With the FAST Method\n\nThe `FAST` method consists of the following 4 steps:\n\n1. Find the first solution\n2. Analyze the solution\n3. Identify the subproblems\n4. Turn around the solution\n\nLet's examine this process with the most popular example when it comes to dynamic programming, calculating the `n`th Fibonacci number:","code":"```\n0, 1, 1, 2, 3, 5, 8, 13,..n\n```","full_screen":false,"solution":"","lesson_id":59,"challenge_id":null,"sequence":4,"title":"Solving With The Fast Method","slug":"solving-with-the-fast-method-4","created_at":"2020-06-04T14:03:39.890Z","updated_at":"2023-01-07T06:04:47.899Z","explanation":null,"summary":"\n\n**Using the `FAST` method can help us break down complex problems into smaller subproblems, such as calculating the `n`th Fibonacci number.**"},{"id":1298,"kind":"info screen","options":[],"content":"The `n`th Fibonacci number is where each number is the sum of the previous `2` numbers. If `F(n)` is the `n`th term of the series then we have `F(n) = F(n-1) + F(n-2)`. For the sake of brevity, we won't go too much into the Mathematical proof. However, this is called a recursive formula or a recurrence relation. We need earlier numbers to have been computed before we can compute a later term.\n\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/intro-to-dynamic-programming/Fib_seq.png\" class=\"img-fluid\" /\u003e","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":5,"title":"Step Five","slug":"step-five-5","created_at":"2020-06-04T14:03:39.996Z","updated_at":"2023-01-07T06:04:49.841Z","explanation":null,"summary":"\nThe Fibonacci sequence is a **recursive formula** where each number is the sum of the previous `2` numbers."},{"id":1299,"kind":"info screen","options":[],"content":"### Finding the First Solution\r\n\r\nThe first step of the FAST method is taking a naive or brute force solution and making it dynamic. So we need to first find that brute force solution for the nth Fibonacci number.\r\n\r\nThis solution is not as efficient as it could be. But it won't matter right now since we're still going to optimize it.","code":"```java\npublic class Main {\n\n    public static int fib(int n) {\n        if (n == 0) return 0;\n        if (n == 1) return 1;\n\n        return fib(n - 1) + fib(n - 2);\n    }\n\n    public static void main(String[] args) {\n        int n = 5;  // Example value\n        System.out.println(\"Fibonacci of \" + n + \" is: \" + fib(n));\n    }\n}\n```\n```javascript\nfunction fib(n) {\n    if (n === 0) return 0;\n    if (n === 1) return 1;\n\n    return fib(n - 1) + fib(n - 2);\n}\n```\n```python\ndef fib(n):\n    if n == 0:\n        return 0\n    if n == 1:\n        return 1\n\n    return fib(n - 1) + fib(n - 2)\n```\n```cpp\n#include \u003ciostream\u003e\n\nint fib(int n) {\n    if (n == 0) return 0;\n    if (n == 1) return 1;\n\n    return fib(n - 1) + fib(n - 2);\n}\n\nint main() {\n    int n = 5;  // Example value\n    std::cout \u003c\u003c \"Fibonacci of \" \u003c\u003c n \u003c\u003c \" is: \" \u003c\u003c fib(n) \u003c\u003c std::endl;\n    return 0;\n}\n```","full_screen":false,"solution":null,"lesson_id":59,"challenge_id":null,"sequence":6,"title":"Finding The First Solution","slug":"finding-the-first-solution-6","created_at":"2020-06-04T14:03:40.101Z","updated_at":"2023-08-17T21:51:44.542Z","explanation":null,"summary":"\r\nWe 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**."},{"id":1300,"kind":"info screen","options":[],"content":"### Analyze the solution\n\nNext, we need to analyze the solution. If we look at the time complexity of our `fib()` function, we see that our solution will take `0(2^n)`. This is a very inefficient runtime. \n\nIf we want to optimize a solution using dynamic programming, it must have an optimal substructure and overlapping subproblems. We know it has overlapping subproblems because if you call `fib(6)`, that will call `fib(5)` and `fib(4)`.\n\n`fib(5)` then recursively calls `fib(4)` and `fib(3)`. From this, it's clear that `fib(4)` is _being called multiple times_ during the execution of `fib(5)`.\n\nIt also has an optimal substructure because we can get the right answer just by combining the result of the subproblems. \n\nWith these characteristics, we know we can use `dynamic programming`!","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":7,"title":"Analyze The Solution","slug":"analyze-the-solution-7","created_at":"2020-06-04T14:03:40.207Z","updated_at":"2023-01-07T06:04:53.629Z","explanation":null,"summary":" Our solution uses **Dynamic Programming** because it has both **overlapping subproblems** and an **optimal substructure**."},{"id":1301,"kind":"info screen","options":[],"content":"### Identify the Subproblems \r\n\r\nThe subproblems are just the recursive calls of `fib(n-1)` and `fib(n-2)`. We know that `fib(n)` is the nth Fibonacci number for any value of n so we have our subproblems. \r\n\r\nWith our subproblems defined, let's memoize the results. This means we're going to save the result of each subproblem as we compute it and then check before computing any value whether or not its already computed. However, this will only require tiny changes to our original solution.","code":"```java\nclass Main {\n    public static int fib(int n) {\n\n        if (n \u003c 2) return n;\n\n        //create cache and initialize it to -1\n        int[] cache = new int[n + 1];\n        for (int i = 0; i \u003c cache.length; i++) {\n            cache[i] = -1;\n        }\n        //fill initial values\n        cache[0] = 0;\n        cache[1] = 1;\n        return fibHelper(n, cache);\n    }\n\n    public static int fibHelper(int n, int[] cache) {\n        //if the value is in the cache return it\n        if (cache[n] \u003e= 0) return cache[n];\n\n        //else compute the result and add it to the cache\n        cache[n] = fibHelper(n - 1, cache) + fibHelper(n - 2, cache);\n        return cache[n];\n    }\n\n    public static void main(String[] args){\n        System.out.println(\"fib(5) = \" + fib(5));\n    }\n}\n\n```\n```javascript\nfunction fib(n) {\n    if (n \u003c 2) return n;\n\n    // create cache and initialize it to -1\n    let cache = new Array(n + 1).fill(-1);\n\n    // fill initial values\n    cache[0] = 0;\n    cache[1] = 1;\n    return fibHelper(n, cache);\n}\n\nfunction fibHelper(n, cache) {\n    // if the value is in the cache return it\n    if (cache[n] \u003e= 0) return cache[n];\n\n    // else compute the result and add it to the cache\n    cache[n] = fibHelper(n - 1, cache) + fibHelper(n - 2, cache);\n    return cache[n];\n}\n\nconsole.log(\"fib(5) =\", fib(5));\n```\n```python\ndef fib(n):\n    if n \u003c 2:\n        return n\n\n    # create cache and initialize it to -1\n    cache = [-1] * (n + 1)\n\n    # fill initial values\n    cache[0] = 0\n    cache[1] = 1\n    return fib_helper(n, cache)\n\ndef fib_helper(n, cache):\n    # if the value is in the cache return it\n    if cache[n] \u003e= 0:\n        return cache[n]\n\n    # else compute the result and add it to the cache\n    cache[n] = fib_helper(n - 1, cache) + fib_helper(n - 2, cache)\n    return cache[n]\n\nprint(\"fib(5) =\", fib(5))\n```\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\nint fib(int n) {\n    if (n \u003c 2) return n;\n\n    // create cache and initialize it to -1\n    std::vector\u003cint\u003e cache(n + 1, -1);\n\n    // fill initial values\n    cache[0] = 0;\n    cache[1] = 1;\n    return fibHelper(n, cache);\n}\n\nint fibHelper(int n, std::vector\u003cint\u003e\u0026 cache) {\n    // if the value is in the cache return it\n    if (cache[n] \u003e= 0) return cache[n];\n\n    // else compute the result and add it to the cache\n    cache[n] = fibHelper(n - 1, cache) + fibHelper(n - 2, cache);\n    return cache[n];\n}\n\nint main() {\n    std::cout \u003c\u003c \"fib(5) = \" \u003c\u003c fib(5) \u003c\u003c std::endl;\n}\n```\n```go\npackage main\n\nimport (\n\t\"fmt\"\n)\n\nfunc fib(n int) int {\n\tif n \u003c 2 {\n\t\treturn n\n\t}\n\n\t// create cache and initialize it to -1\n\tcache := make([]int, n+1)\n\tfor i := range cache {\n\t\tcache[i] = -1\n\t}\n\n\t// fill initial values\n\tcache[0] = 0\n\tcache[1] = 1\n\treturn fibHelper(n, cache)\n}\n\nfunc fibHelper(n int, cache []int) int {\n\t// if the value is in the cache return it\n\tif cache[n] \u003e= 0 {\n\t\treturn cache[n]\n\t}\n\n\t// else compute the result and add it to the cache\n\tcache[n] = fibHelper(n-1, cache) + fibHelper(n-2, cache)\n\treturn cache[n]\n}\n\nfunc main() {\n\tfmt.Println(\"fib(5) =\", fib(5))\n}\n```","full_screen":false,"solution":null,"lesson_id":59,"challenge_id":null,"sequence":8,"title":"Identify The Subproblems","slug":"identify-the-subproblems-8","created_at":"2020-06-04T14:03:40.312Z","updated_at":"2023-08-17T22:37:33.689Z","explanation":null,"summary":" \r\n**We identify the subproblems as `fib(n-1)` and `fib(n-2)` in order to `memoize` them and save results.**"},{"id":1302,"kind":"info screen","options":[],"content":"In this solution, we are creating a `cache` or an array to store our solutions. If there is an already computed solution in the cache, then we would just return it else we compute the result and add it to the cache. \n\nFor example, if we are calculating `fib(4)`, the subproblems are `fib(3)` and `fib(2)`. These solutions are then stored in the cache. Then, when we are calculating `fib(3)`, our program checks to see if `fib(2)` and `fib(1)` were already stored inside the cache. We would continue until we hit our base case when our value `n` is less than 2.\n\nOur new solution only has to compute each value once, so it runs in `O(n)` time complexity and `O(n)` space complexity because of the cache.","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":9,"title":"Step Nine","slug":"step-nine-9","created_at":"2020-06-04T14:03:40.418Z","updated_at":"2023-01-07T06:05:02.010Z","explanation":null,"summary":" 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)`."},{"id":1303,"kind":"info screen","options":[],"content":"### Turn around the situation\n\nThe final step is to make our solution iterative. With the previous (top-down) solution, we started with n and then repeatedly broke it down into smaller and smaller values until we reached `n == 0` and `n == 1`. Instead, we will start with the base case and work our way up.","code":"```java\npublic class Main {\n    public static int fib(int n) {\n\n        if (n == 0) return 0;\n\n        //initialize cache\n        int[] cache = new int[n + 1];\n        cache[1] = 1;\n\n        //iteratively fill cache\n        for (int i = 2; i \u003c= n; i++) {\n            cache[i] = cache[i - 1] + cache[i - 2];\n        }\n        return cache[n];\n    }\n\n    public static void main(String[] args) {\n        System.out.println(fib(5));\n    }\n}\n```\n```javascript\nfunction fib(n) {\n    if (n === 0) return 0;\n\n    // initialize cache\n    let cache = new Array(n + 1).fill(0);\n    cache[1] = 1;\n\n    // iteratively fill cache\n    for (let i = 2; i \u003c= n; i++) {\n        cache[i] = cache[i - 1] + cache[i - 2];\n    }\n    return cache[n];\n}\n\nconsole.log(fib(5));\n```\n```python\ndef fib(n):\n    if n == 0:\n        return 0\n\n    # initialize cache\n    cache = [0] * (n + 1)\n    cache[1] = 1\n\n    # iteratively fill cache\n    for i in range(2, n + 1):\n        cache[i] = cache[i - 1] + cache[i - 2]\n    return cache[n]\n\nprint(fib(5))\n```\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\nint fib(int n) {\n    if (n == 0) return 0;\n\n    // initialize cache\n    std::vector\u003cint\u003e cache(n + 1, 0);\n    cache[1] = 1;\n\n    // iteratively fill cache\n    for (int i = 2; i \u003c= n; i++) {\n        cache[i] = cache[i - 1] + cache[i - 2];\n    }\n    return cache[n];\n}\n\nint main() {\n    std::cout \u003c\u003c fib(5) \u003c\u003c std::endl;\n    return 0;\n}\n```\n```go\npackage main\n\nimport (\n\t\"fmt\"\n)\n\nfunc fib(n int) int {\n\tif n == 0 {\n\t\treturn 0\n\t}\n\n\t// initialize cache\n\tcache := make([]int, n+1)\n\tcache[1] = 1\n\n\t// iteratively fill cache\n\tfor i := 2; i \u003c= n; i++ {\n\t\tcache[i] = cache[i-1] + cache[i-2]\n\t}\n\treturn cache[n]\n}\n\nfunc main() {\n\tfmt.Println(fib(5))\n}\n```","full_screen":false,"solution":"","lesson_id":59,"challenge_id":null,"sequence":10,"title":"Turn Around The Situation","slug":"turn-around-the-situation-10","created_at":"2020-06-04T14:03:40.524Z","updated_at":"2023-08-17T21:53:56.637Z","explanation":null,"summary":"\nWe will **`iteratively`** build from the base case and `work our way up` to solve the problem."},{"id":1304,"kind":"info screen","options":[],"content":"This process follows a bottom-up (iterative) solution. Since we are iterating through all of the numbers from `0` to `n` just once, our time complexity is `O(n)` and our space complexity will also be `O(n)`. This is similar to our top-down solution just without the recursion. This solution is likely easier to understand and is more intuitive.","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":11,"title":"Step Eleven","slug":"step-eleven-11","created_at":"2020-06-04T14:03:40.630Z","updated_at":"2023-01-07T06:05:06.013Z","explanation":null,"summary":" 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."},{"id":4286,"kind":"swipe","options":[],"content":"All problems that can be solved using top-down approach can also be solved using bottom-up approach in dynamic programming.","code":null,"full_screen":false,"solution":"true","lesson_id":59,"challenge_id":null,"sequence":12,"title":"True or False","slug":"true-or-false","created_at":"2021-12-31T18:25:07.304Z","updated_at":"2023-01-07T06:05:13.748Z","explanation":"\nYes, all problems that can be solved using top-down dynamic programming approach can also be solved using bottom-up dynamic programming approach. The main idea behind dynamic programming is **breaking down a problem into smaller subproblems**, solving them and combining them together to get **the optimal solutions**. A top-down approach requires **solving the subproblems one at a time with an iterative or recursive approach**, while a bottom-up approach requires **solving the subproblems in a pre-defined order, starting with the smallest problem**. Both of these approaches can be used to obtain the same solutions, although the top-down approach may be more intuitive while the bottom-up approach may be more efficient.","summary":" 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`."},{"id":4285,"kind":"fill in","options":[],"content":"Solving a problem using the FAST method of dynamic programming always increases the ___ complexity of the algorithm.","code":null,"full_screen":false,"solution":"space","lesson_id":59,"challenge_id":null,"sequence":13,"title":"Fill In","slug":"fill-in","created_at":"2021-12-31T18:07:42.042Z","updated_at":"2023-01-07T06:05:19.930Z","explanation":"\nThe **FAST** method of dynamic programming is an acronym for Forward Algorithm \u0026 Space-Time Tradeoff. This method focuses on **reducing the time complexity** of the algorithm, usually by trading off **extra memory (space) requirements**. By allocating **additional space to store data**, the algorithm can **reduce the time** it takes to solve the problem. Therefore, solving a problem using the FAST method of dynamic programming increases the **space complexity** of the algorithm.","summary":" 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."},{"id":1305,"kind":"info screen","options":[],"content":"### Solving Dynamic Programming problems--A more intuitive approach\r\n\r\n\u003cimg src=\"https://storage.googleapis.com/algodailyrandomassets/intro-to-dynamic-programming/HouseRobber.png\" class=\"img-fluid\" /\u003e\r\n\r\nAnother popular dynamic programming question is the `House Robber problem`.\r\n\r\nThe idea here is that robbers want to rob houses along a street and their only constraint is that they can't rob `2` adjacent houses. So what we need to do is to calculate the maximum amount of money that they can rob up to any point. Eventually, if they can propagate the max amount of money to rob at the `i'th` house and the `i` eventually becomes the last house then we can know the max amount of money we can get.\r\n\r\nA good way to start thinking about this is to consider how much money can they make if they rob `0` houses? Obviously, the answer would be `0`. We can slowly start thinking about how much money can be robbed from `1` house, `2` houses, `3` houses and so on. Eventually, that will give us `n` houses.\r\n\r\nSo back to the first case. If we rob `0` houses then we will make $0.","code":"```java\nclass Main {\n    public int rob(int[] nums) {\n            int len = nums.length;\n            if (len == 0) return 0;\n```\n```javascript\nfunction rob(nums) {\n    let len = nums.length;\n    if (len === 0) return 0;\n    // ...\n}\n```\n```python\ndef rob(nums):\n    len_nums = len(nums)\n    if len_nums == 0:\n        return 0\n    # ...\n```\n```cpp\n#include \u003cvector\u003e\n\nclass Main {\npublic:\n    int rob(std::vector\u003cint\u003e\u0026 nums) {\n        int len = nums.size();\n        if (len == 0) return 0;\n        // ...\n    }\n};\n```\n```go\nfunc rob(nums []int) int {\n    lenNums := len(nums)\n    if lenNums == 0 {\n        return 0\n    }\n    // ...\n}\n```\n","full_screen":false,"solution":null,"lesson_id":59,"challenge_id":null,"sequence":14,"title":"Solving Dynamic Programming Problems  A More Intuitive Approach","slug":"step-twelve-12","created_at":"2020-06-04T14:03:40.736Z","updated_at":"2023-08-17T21:55:30.028Z","explanation":null,"summary":" 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."},{"id":1306,"kind":"info screen","options":[],"content":"If we rob one house then, we would just take what that house has.\n\n```java\nif(len == 1) return nums[0];\n```\n```javascript\nif (len === 1) return nums[0];\n```\n```python\nif len_nums == 1:\n    return nums[0]\n```\n```cpp\nif (len == 1) return nums[0];\n```\n```go\nif lenNums == 1 {\n    return nums[0]\n}\n```\n","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":15,"title":"Step Thirteen","slug":"step-thirteen-13","created_at":"2020-06-04T14:03:40.842Z","updated_at":"2023-09-20T23:45:31.580Z","explanation":null,"summary":" We would `rob` only `one house` and take **what it has**."},{"id":1307,"kind":"info screen","options":[],"content":"But if we have `2` houses it becomes a little more interesting. But it's still pretty simple. If house A has more money, we rob house A. But if house B has more money we rob house B.\n\n```java\nif(len == 2) return Math.max(nums[0], nums[1]);\n```\n```javascript\nif (len === 2) return Math.max(nums[0], nums[1]);\n```\n```python\nif len_nums == 2:\n    return max(nums[0], nums[1])\n```\n```cpp\nif (len == 2) return std::max(nums[0], nums[1]);\n```\n```go\nif lenNums == 2 {\n    if nums[0] \u003e nums[1] {\n        return nums[0]\n    }\n    return nums[1]\n}\n```\n","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":16,"title":"Step Fourteen","slug":"step-fourteen-14","created_at":"2020-06-04T14:03:40.949Z","updated_at":"2023-09-20T23:45:21.764Z","explanation":null,"summary":" `If house A has more money, we rob house A; otherwise, we rob house B.`"},{"id":1308,"kind":"info screen","options":[],"content":"When we have `3` houses it becomes a little less intuitive and this is where the dynamic programming comes in. Particularly the bottom up(iterative) process. If we are searching for the `nth` answer, we can solve a smaller subproblem for the `ith` answer to solve for n.","code":"```java\nint[] arr = new int[len];\n\narr[0] = nums[0];\n\narr[1] = Math.max(nums[0], nums[1]);\n\nfor (int i = 2; i \u003c len; i++) {\n    arr[i] = Math.max(arr[i - 2] + nums[i], arr[i - 1]);\n}\nreturn arr[arr.length - 1];\n```\n```javascript\nlet arr = new Array(len);\narr[0] = nums[0];\narr[1] = Math.max(nums[0], nums[1]);\nfor (let i = 2; i \u003c len; i++) {\n    arr[i] = Math.max(arr[i - 2] + nums[i], arr[i - 1]);\n}\nreturn arr[arr.length - 1];\n```\n```python\narr = [0] * len_nums\narr[0] = nums[0]\narr[1] = max(nums[0], nums[1])\nfor i in range(2, len_nums):\n    arr[i] = max(arr[i - 2] + nums[i], arr[i - 1])\nreturn arr[-1]\n```\n```cpp\nstd::vector\u003cint\u003e arr(len);\narr[0] = nums[0];\narr[1] = std::max(nums[0], nums[1]);\nfor (int i = 2; i \u003c len; i++) {\n    arr[i] = std::max(arr[i - 2] + nums[i], arr[i - 1]);\n}\nreturn arr[arr.size() - 1];\n```\n```go\narr := make([]int, lenNums)\narr[0] = nums[0]\nif nums[0] \u003e nums[1] {\n    arr[1] = nums[0]\n} else {\n    arr[1] = nums[1]\n}\nfor i := 2; i \u003c lenNums; i++ {\n    if arr[i-2]+nums[i] \u003e arr[i-1] {\n        arr[i] = arr[i-2] + nums[i]\n    } else {\n        arr[i] = arr[i-1]\n    }\n}\nreturn arr[len(arr)-1]\n```","full_screen":false,"solution":"","lesson_id":59,"challenge_id":null,"sequence":17,"title":"Step Fifteen","slug":"step-fifteen-15","created_at":"2020-06-04T14:03:41.055Z","updated_at":"2023-08-17T22:32:03.970Z","explanation":null,"summary":"\nThe `bottom-up (iterative)` process of **dynamic programming** can be utilized to solve for the `nth` answer by solving smaller subproblems for the `ith` answer."},{"id":1309,"kind":"info screen","options":[],"content":"The code put together would look like:","code":"```java\nclass Main {\n    public static int rob(int[] nums) {\n\n        int len = nums.length;\n\n        if (len == 0) return 0;\n\n        if (len == 1) return nums[0];\n        if (len == 2) return Math.max(nums[0], nums[1]);\n\n        int[] arr = new int[len];\n\n        arr[0] = nums[0];\n        arr[1] = Math.max(nums[0], nums[1]);\n\n        for (int i = 2; i \u003c len; i++) {\n\n            arr[i] = Math.max(arr[i - 2] + nums[i], arr[i - 1]);\n        }\n\n        return arr[arr.length - 1];\n\n    }\n\n    public static void main(String[] args){\n        int[] arr = {4, 8, 0, 1};\n        System.out.println(rob(arr));\n    }\n}\n\n```\n```javascript\nfunction rob(nums) {\n    let len = nums.length;\n\n    if (len === 0) return 0;\n    if (len === 1) return nums[0];\n    if (len === 2) return Math.max(nums[0], nums[1]);\n\n    let arr = new Array(len);\n    arr[0] = nums[0];\n    arr[1] = Math.max(nums[0], nums[1]);\n\n    for (let i = 2; i \u003c len; i++) {\n        arr[i] = Math.max(arr[i - 2] + nums[i], arr[i - 1]);\n    }\n\n    return arr[len - 1];\n}\n\nlet arr = [4, 8, 0, 1];\nconsole.log(rob(arr));\n```\n```python\ndef rob(nums):\n    len_nums = len(nums)\n\n    if len_nums == 0:\n        return 0\n    if len_nums == 1:\n        return nums[0]\n    if len_nums == 2:\n        return max(nums[0], nums[1])\n\n    arr = [0] * len_nums\n    arr[0] = nums[0]\n    arr[1] = max(nums[0], nums[1])\n\n    for i in range(2, len_nums):\n        arr[i] = max(arr[i - 2] + nums[i], arr[i - 1])\n\n    return arr[-1]\n\narr = [4, 8, 0, 1]\nprint(rob(arr))\n```\n```cpp\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n\nint rob(std::vector\u003cint\u003e\u0026 nums) {\n    int len = nums.size();\n\n    if (len == 0) return 0;\n    if (len == 1) return nums[0];\n    if (len == 2) return std::max(nums[0], nums[1]);\n\n    std::vector\u003cint\u003e arr(len);\n    arr[0] = nums[0];\n    arr[1] = std::max(nums[0], nums[1]);\n\n    for (int i = 2; i \u003c len; i++) {\n        arr[i] = std::max(arr[i - 2] + nums[i], arr[i - 1]);\n    }\n\n    return arr[len - 1];\n}\n\nint main() {\n    std::vector\u003cint\u003e arr = {4, 8, 0, 1};\n    std::cout \u003c\u003c rob(arr) \u003c\u003c std::endl;\n    return 0;\n}\n```\n```go\npackage main\n\nimport (\n\t\"fmt\"\n)\n\nfunc rob(nums []int) int {\n    lenNums := len(nums)\n\n    if lenNums == 0 {\n        return 0\n    }\n    if lenNums == 1 {\n        return nums[0]\n    }\n    if lenNums == 2 {\n        if nums[0] \u003e nums[1] {\n            return nums[0]\n        }\n        return nums[1]\n    }\n\n    arr := make([]int, lenNums)\n    arr[0] = nums[0]\n    if nums[0] \u003e nums[1] {\n        arr[1] = nums[0]\n    } else {\n        arr[1] = nums[1]\n    }\n\n    for i := 2; i \u003c lenNums; i++ {\n        if arr[i-2]+nums[i] \u003e arr[i-1] {\n            arr[i] = arr[i-2] + nums[i]\n        } else {\n            arr[i] = arr[i-1]\n        }\n    }\n\n    return arr[lenNums-1]\n}\n\nfunc main() {\n    nums := []int{4, 8, 0, 1}\n    fmt.Println(rob(nums))\n}\n```","full_screen":false,"solution":null,"lesson_id":59,"challenge_id":null,"sequence":18,"title":"Step Sixteen","slug":"step-sixteen-16","created_at":"2020-06-04T14:03:41.161Z","updated_at":"2023-08-17T22:30:52.030Z","explanation":null,"summary":"\nThe code `put together` would **look like** `this`."},{"id":1310,"kind":"info screen","options":[],"content":"The idea behind this solution is to solve the problem for simpler cases to help solve the larger problem(bottom-up process). We created an array `arr` where `arr[i]` will represent the max amount of money we can rob up to and including the current house. Once we populate the array, we simply return the last entry which represents the max amount of money we can rob given the constraints.","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":19,"title":"Step Seventeen","slug":"step-seventeen-17","created_at":"2020-06-04T14:03:41.267Z","updated_at":"2023-01-07T06:05:35.166Z","explanation":null,"summary":" 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."},{"id":4289,"kind":"swipe","options":[],"content":"Dynamic programming can provide an optimal solution if and only if there is knowledge of previous and current states.","code":null,"full_screen":false,"solution":"false","lesson_id":59,"challenge_id":null,"sequence":20,"title":"True or False","slug":"true-or-false2","created_at":"2021-12-31T19:02:00.432Z","updated_at":"2023-01-07T06:05:46.523Z","explanation":"The core component of dynamic programming involves **storing the solutions of subproblems**, which can then be used to solve the larger problem. This means that it can be used to solve problems that do not necessarily have knowledge of previous and current states. Instead, what is important is that the problem can be divided into subproblems that are repeated. As long as these subproblems can be broken down and solved independently, they can be built upon in order to solve the overall problem.  In the case described, the larger problem is broken down into smaller subproblems, such as **calculating the maximum amount of money we can rob for each house up to a certain point**. This does not require knowledge of previous and current states, rather it requires the ability to divide the problem into smaller questions which can each be answered.","summary":" 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**."},{"id":1311,"kind":"info screen","options":[],"content":"## Conclusion\n\nDynamic Programming doesn't have to be scary. Following the `FAST` method can get you to an optimal solution as long as you can come up with an initial brute force solution. However, just knowing the theory isn't enough, to build confidence and proficiency in dynamic programming you must practice programming by doing.","code":"","full_screen":true,"solution":"","lesson_id":59,"challenge_id":null,"sequence":21,"title":"Conclusion","slug":"conclusion-18","created_at":"2020-06-04T14:03:41.373Z","updated_at":"2023-01-07T06:05:47.985Z","explanation":null,"summary":"\nWith `FAST` and enough practice, **Dynamic Programming** can be used to reach an optimal solution."},{"id":4287,"kind":"order","options":["Initialize an array"," Add base case"," Fill array using recursive formula"," Loop from 0...n "],"content":"Order the steps for the following problem, solved using dynamic programming.\n\nGiven `n` friends, each one can remain single or can be paired up with some other friend. Each friend can be paired only once. Find out the total number of ways in which friends can remain single or can be paired up. ","code":null,"full_screen":false,"solution":"[0, 3, 1, 2]","lesson_id":59,"challenge_id":null,"sequence":22,"title":"Order Sequence","slug":"order-sequence","created_at":"2021-12-31T18:50:42.830Z","updated_at":"2023-01-07T06:05:58.382Z","explanation":"1. **Initialize an array**: Before attempting to solve the dynamic programming problem, the first step is to create an array and assign it the necessary dimensions to store the data that will be created from solving the problem. \n\n2. **Loop from 0...n**: After the array has been initialized, the next step is to loop through the array from 0 till n, where `n` is the number of friends as described in the problem. \n\n3. **Add base case**: Once the looping is complete, the next step is to add the **base case** of the problem. The base case is a special instance of the problem that is easy to solve and provides a starting point for the more complex problems. \n\n4. **Fill array using recursive formula**: Finally, the last step is to fill the array by using the **recursive formula** to calculate a solution for the dynamic programming problem. The recursive formula allows the computational power of dynamic programming to be used for solving problems that cannot be solved using traditional methods.","summary":" 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**."},{"id":5571,"kind":"info screen","options":[],"content":"## One Pager Cheat Sheet\n\n- 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.\n- `Dynamic Programming` helps us save time by **remembering information**.\n- **Using the `FAST` method can help us break down complex problems into smaller subproblems, such as calculating the `n`th Fibonacci number.**\n- The Fibonacci sequence is a **recursive formula** where each number is the sum of the previous `2` numbers.\n- 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**.\n- Our solution uses **Dynamic Programming** because it has both **overlapping subproblems** and an **optimal substructure**.\n- **We identify the subproblems as `fib(n-1)` and `fib(n-2)` in order to `memoize` them and save results.**\n- 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)`.\n- We will **`iteratively`** build from the base case and `work our way up` to solve the problem.\n- 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.\n- 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`.\n- 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.\n- 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.\n- We would `rob` only `one house` and take **what it has**.\n- `If house A has more money, we rob house A; otherwise, we rob house B.`\n- 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.\n- The code `put together` would **look like** `this`.\n- 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.\n- 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**.\n- With `FAST` and enough practice, **Dynamic Programming** can be used to reach an optimal solution.\n- 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**.","code":null,"full_screen":true,"solution":null,"lesson_id":59,"challenge_id":null,"sequence":23,"title":"One Pager Cheat Sheet","slug":"algodaily-cheatsheet","created_at":"2023-01-07T06:03:44.289Z","updated_at":"2023-01-07T06:03:44.289Z","explanation":null,"summary":null}],"beforeArr":["Challenge","nested-list-weight-sum"],"nextArr":["Lesson","what-is-bottom-up-dynamic-programming"],"section":{"id":22,"title":"Dynamic Programming Interview Questions","slug":"dynamic-programming-interview-questions","sequence":20,"description":"Dynamic programming is both a mathematical optimization method and a computer programming method that breaks down complicated problems to sub-problems. Dynamic programming uses recursion to solve problems which would be solved iteratively in an equivalent tree or network model. The technique was introduced by Richard Bellman (1952), who used it to solve a variety of problems including those in the fields of mathematics, economics, statistics, engineering, accounting, linguistics and other areas of science.\n\nDynamic programming solves a problem by breaking it down into subproblems and storing their solutions as part of the original problem's solution. The approach works by first solving each subproblem as if it were the only one; that is done by solving only for the first variable in each subproblem. Then, all values from all subproblems are summed up together to get the final solution for the entire original problem. This technique is known as \"memoization\".\n\nEven if you never encounter them, the concepts learned are useful for solving many other kinds of coding challenges. Let's practice some dynamic programming problems!","created_at":"2021-04-29T02:39:50.930Z","updated_at":"2022-08-15T20:15:07.100Z","image_url":"https://storage.googleapis.com/algodailyrandomassets/curriculum/multistep/sum-of-perfect-squares/sum_of_perfect_squares-1.png","course_id":3,"published":true,"locked":true,"time":"2.5 hours","code_snippets_count":57,"visuals_count":30,"free_tutorials":4,"videos_count":0},"course":{"id":3,"title":"Data Structures and Algorithms 🚀","image_url":"https://storage.googleapis.com/algodailyrandomassets/tutorials-optimized/find-duplicate-words-cover-image.png","description":"The _O.G._ of all of our material, this jam-packed course presents all the necessary data structures and algorithmic concepts you need to know for any whiteboard interview.\n\nWith our award-winning visual and interactive method, we break down tough and complex algorithms into simple steps you can follow. Data structures become your friend once you see them in action, and understand the beauty of their implementations.\n\nOver 25k developers have used this course to finally \"see\" algorithmic patterns and utilize them on interview game-day. Try it out for yourself, and de-mystify this cornerstone aspect of Computer Science.","slug":"data-structures-and-algorithms","mini_course":false,"sequence":4,"user_id":1,"created_at":"2021-06-18T21:19:08.152Z","updated_at":"2023-08-17T13:45:29.523Z","published":true,"time":"45.2 hours","author_details":null,"difficulty":6,"lessons_count":44,"challenges_count":141,"code_snippets_count":1334,"visuals_count":633,"free_tutorials":81,"users_taking":40245,"locked":true,"videos_count":46,"newsletter_title":"AlgoDaily DS \u0026 Algos","kind":"essentials","status":null,"user_background":null,"language":null,"interest_string":null},"screen_completions":[]}