![]() The optimal substructure property comes in whereby the overall optimal solution is constructed using optimal solutions of the subproblems. Can you spot the overlapping subproblems from the previous recurrence tree? Our problem has overlapping subproblems in that finding the global solution involves solving the same subproblem multiple times. Generally a dynamic programming problem has the following characteristics In this approach the algorithm will optimize the naive recursive solution to a quadratic time complexity which is a little bit better.īefore we get to it, a little about dynamic programming, we use dynamic programming to optimize recursive problems whereby we call a recursive function for repeated inputs which results in unnecessary re-computations. Space complexity is O(1) without including the stack space used for the recursive calls.Īpproach 2: Dynamic programming (Bottom Up).The time complexity is O ( 2 n ), that is there are n possible ways to move from an element for each element in the list.Traverse through the list, from start index recursively call for elements reachable from start index until minimum is found.We shall see how to avoid them in the next approach. That is, it will explore all branches in the recursion tree and return the minimum number of jumps to reach the last index.Īs you can see there are repeated re-computations of same values. The algorithm will recursively call for all elements reachable from the first element. ![]() The base case will be triggered when the algorithm reaches the last index, then the algorithm terminates. In this approach we will use recursion to solve the problem. The goal is to reach the last index in the minimum number of jumps.Īssume that you can always reach the last index. We are given an array of non-negative integers, initially we are positioned at the first index of the array.Įach element represents the maximum jump length from that position to another. This problem is similar to Leetcode problem 45. Prerequisite: Dynamic Programming, Greedy Algorithm, nth Fibonacci
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |