{"id":2229,"date":"2020-01-31T02:37:08","date_gmt":"2020-01-31T02:37:08","guid":{"rendered":"http:\/\/kusuaks7\/?p=1834"},"modified":"2024-01-22T12:06:44","modified_gmt":"2024-01-22T12:06:44","slug":"dynamic-programming-for-data-scientists","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/bigdata-cloud\/dynamic-programming-for-data-scientists\/","title":{"rendered":"Dynamic Programming for Data Scientists"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tAlgorithms and data structures are an integral part of data science. While most of us data scientists don\u2019t take a proper algorithms course while studying, they are important all the same.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nMany companies ask data structures and algorithms as part of their interview process for hiring data scientists.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tNow the question that many people ask here is what is the use of asking a data scientist such questions.\u00a0The way I like to describe it is that a data structure question may be thought of as a coding aptitude test.<\/em><\/strong>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tWe all have given aptitude tests at various stages of our life, and while they are not a perfect proxy to judge someone, almost nothing ever really is.<\/em>\u00a0So, why not a standard algorithm test to judge people\u2019s coding ability.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tBut let\u2019s not kid ourselves, they will require the same zeal to crack as your Data Science interviews, and thus, you might want to give some time for the study of algorithms and Data structure and algorithms questions.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nThis post is about fast-tracking this study and explaining Dynamic Programming concepts for the data scientists in an easy to understand way.<\/em><\/strong>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t

\n

How Dynamic Programming Works?<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tLet\u2019s say that we need to find the nth Fibonacci Number.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tFibonacci series is a series of numbers in which each number (\u00a0Fibonacci number<\/em>\u00a0) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc. The answer is:\n
def fib(n):\nif n<=1:\nreturn 1\nreturn fib(n-1) + fib(n-2)<\/code><\/pre>\nThis problem relates well to a recursive approach. But can you spot the problem here?\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tIf you try to calculate fib(n=7) it runs fib(5) twice, fib(4) thrice, fib(3) five times. As n becomes larger, a lot of calls are made for the same number, and our recursive function calculates it again and again.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
Source<\/a><\/em><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tNow, Recursion is essentially a top-down approach. As in when calculating Fibonacci number n we start from n and then do recursive calls for n-2 and n-1 and so on.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tIn\u00a0Dynamic programming<\/em><\/strong>, we take a bottom-up approach. It is essentially a way to write recursion iteratively. We start by calculating fib(0) and fib(1) and then use previous results to generate new results.\n
def fib_dp(n):\ndp_sols = {0:1,1:1}\nfor i in range(2,n+1):\ndp_sols[i] = dp_sols[i-1] + dp_sols[i-2]\nreturn dp_sols[n]<\/code><\/pre>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
Why Dynamic Programming is Hard?<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tRecursion is a mathematical concept and it comes naturally to us. We try to find a solution to a bigger problem by breaking it into smaller ones.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tNow Dynamic Programming entails exactly the same idea but in the case of Dynamic programming, we precompute all the subproblems that might need to be calculated in a bottom-up manner.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tWe human beings are essentially hard-wired to work in a top-down manner. Be it our learning where most people try to go into the breadth of things before going in-depth. Or be it the way we think.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tSo how does one start thinking in a bottom-up way?\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tI found out that solving the below problem gives a lot of intuition in how DP works.<\/em><\/strong>\u00a0I myself got highly comfortable with DP once I was able to solve this one and hope it helps you too.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nBasically the idea is if you can derive\/solve a bigger subproblem if you know the solution to a smaller one?\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
Maximum Path Sum<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tGiven a\u00a0m<\/em>\u00a0x\u00a0n<\/em>\u00a0grid filled with gold, find a path from top left to bottom right which\u00a0maximizes<\/em>\u00a0the sum of gold along its path. We can only move down or right starting from (0,0)\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tNow there can be decidedly many paths. We can go all the way to the right and then the bottom. Or we can take a zigzag path?\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tBut only one\/few paths are going to make you rich.\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tSo how do you even start thinking about such a problem?\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nWhen we think of Dynamic Programming questions, we take a bottom-up approach. So we start by thinking about the simplest of problems. In our case, the simplest of problems to solve is the base case. What is the maximum value of Gold we can acquire if we just had to reach cell (0,0)?\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\nAnd the answer to that is pretty simple \u2014 It is the cell value itself.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tSo we move on to a little harder problem.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tWhat about cell (0,1) and cell (1,0)?\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tThese are also pretty simple. We can reach (0,1)and (1,0) through only (0,0) and hence the maximum gold we can obtain is the value in cell (0,1)\/(1,0) plus the maximum gold we can have when we reach cell(0,0)\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tWhat about cell(0,2)? Again only one path. So if we know the solution to (0,1) we can just add the value of cell (0,2) to get the solution for (0,2)\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tLet\u2019s now try to do the same for an arbitrary cell. We want to derive a relation here.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tSo in the case of an arbitrary cell, we can reach it from the top or from the left.<\/em><\/strong>If we know the solutions to the top and left of the cell, we can definitely compute the solution to the arbitrary current target cell.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
Coding<\/h3><\/h3>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tOnce we have the intuition the coding exercise is pretty straightforward. We start by calculating the solutions for the first row and first column. And then we continue to calculate the other values in the grid using the relation we got previously.\n
def maxPathSum(grid):\nm = len(grid)\nn = len(grid[0])\n# sol keeps the solutions for each point in the grid.\nsol = list(grid)\n# we start by calculating solutions for the first row\nfor i in range(1,n):\nsol[0][i] += sol[0][i-1]\n# we then calculate solutions for the first column\nfor i in range(1,m):\nsol[i][0] += sol[i-1][0]\n# we then calculate all the solutions in the grid\nfor i in range(1,m):\nfor j in range(1,n):\nsol[i][j] += max(sol[i-1][j],sol[i][j-1])\n# return the last element\nreturn sol[-1][-1]<\/code><\/pre>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n
Conclusion<\/h2><\/h2>\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tIn this post, I talked about how I think about Dynamic Programming questions.<\/em><\/strong>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tI start by asking myself the simplest problem I could solve and if I can solve the bigger problem by using the solutions to the simpler problem.<\/em><\/strong>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tDynamic Programming forms the basis of some of the most asked questions in Data Science\/Machine Learning job interviews, and a good understanding of these might help you land your dream job.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\tSo go out there and do some problems with Leetcode\/HackerRank. The problems are surely interesting.\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
Dynamic Programming forms the basis of some of the most asked questions in Data Science\/Machine Learning job interviews, and a good understanding of these might help you land your dream job. In Dynamic programming, we take a bottom-up approach. It is essentially a way to write recursion iteratively. Recursion is a mathematical concept and it comes naturally to us. This post is about study and explaining Dynamic Programming concepts for the data scientists in an easy to understand way.<\/p>\n","protected":false},"author":653,"featured_media":3537,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"content-type":"","footnotes":""},"categories":[187],"tags":[94],"ppma_author":[3409],"class_list":["post-2229","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bigdata-cloud","tag-data-science"],"authors":[{"term_id":3409,"user_id":653,"is_guest":0,"slug":"rahul-agarwal","display_name":"Rahul Agarwal","avatar_url":"https:\/\/www.experfy.com\/blog\/wp-content\/uploads\/2020\/04\/medium_cc5785b8-8195-44e6-a0de-2e33be05d7cb-150x150.png","user_url":"http:\/\/bit.ly\/384SBYb","last_name":"Agarwal","first_name":"Rahul","job_title":"","description":"Rahul Agarwal is a Data Scientist at Walmart Labs."}],"_links":{"self":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/2229","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/users\/653"}],"replies":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/comments?post=2229"}],"version-history":[{"count":4,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/2229\/revisions"}],"predecessor-version":[{"id":35573,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/2229\/revisions\/35573"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media\/3537"}],"wp:attachment":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media?parent=2229"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/categories?post=2229"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/tags?post=2229"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=2229"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}