在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
开源软件名称:nobodyme/dynamic-programming开源软件地址:https://github.com/nobodyme/dynamic-programming开源编程语言:C 100.0%开源软件介绍:Dynamic ProgrammingThere were a huge number of sources on the internet on this topic but still, we (me and my friend) couldn't understand any of it for a very long time until we fiddled with code and tracked the output for every change in the input. So this repository is exactly created for people like us to make the transition from greedy to dynamic programming easier. This will just be an introduction to dynamic programming so that one can pick it up from there. I have added additional sources for practice and other online tutorials that I found a little helpful at the end and will continue to do so as I find something new. It is for programmers who are comfortable with brute force and might not serve the purpose of absolute beginners. Contributions or suggestions are welcome. DefinitionSo what's dynamic programming? Let's first look at a more formal definition. Dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, to facilitate its lookup)(Source-Wiki). Or more simply, it is technique to save intermediate results in a calculation in any comfortable format so that the result can be used for further computation instead of calculating it all over again at the arrival of additional input. Sounds simple enough? Yes, indeed it is, let's have a look at an example to put it right through our skull. Before that, we need to identify whether a problem has the following properties, inorder to be solved by Dynamic Programming(DP) Problems:Minimum cost problemGiven a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0). Each cell of the matrix represents a cost to traverse through that cell. The total cost of a path to reach (m, n) is the sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.
(forgive the highlighting of the first row it is of no special significance) Solution: Me: So how would you go on solving that? How would you normally solve it, forgetting about code for a minute? That's pretty much it. My friend interrupts, So what do we know so far?
Breaking down the problem: Me: What is simply the cost of moving from [0,0] to [0,1]?
Why not code it up too?
where n is the number of rows We transfer the first element as it is to the Friend: Why not the columns? The cells in the first column have only one way of reaching them too, which is down from the first cell. Similarly, we calculate the cost of reaching each column by adding the cell with the previous ones in the column.
We'll code that up too!
where m is the number of columns Friend: Now, how do we calculate the minimum cost to reach cell [1,1]? So the Similarly, we do for all cells, starting from 1,1. Let's code it up again,
Now that our table is filled, we simply return the cell of the given destination in the minimum cost array. The full code is given here. Here is a similar problem, try it on your own and another similar problem is added in the repository. Hence by considering the elements one by one we have built up our solution or in DP terms, we have acquired our solution in bottom-up fashion(tabulation method) from the sub-problems. There's another approach to it called memoization. The difference between both is explained in the article over here. Longest increasing subsequenceThe Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 12, 32, 2, 22, 23, 25, 30} is 6 and LIS is {10, 12, 22, 23, 25, 30} Solution: How would go on solving this problem? What would you store to make the calculations easier? Okay simply, how would you solve the above problem using brute force just like how you would perform a selection sort!
Friend: I would compare every element with every other element, if it's greater than the current one, I would increase the count variable and I would print the highest count, I get. Roughly I would code it something like this pseudo code (It's okay if you don't understand my friend's code)
Me: Let's run it. Me: Because while traversing {10, 12, 32, 22, 23, 25, 30} the code will run as follows,it will check, Friend: If only it knew that by avoiding 32 and traversing through the rest of the array we would actually obtain the result which is NOTE: And my friend has set count=1 and not 0 initially because when we have a case where all numbers are the same in the array i.e {2, 2, 2, 2}. We must return count as 1 since one element { 2 } is still a subarray of the larger one. Dp solution: Me: So how would you code the same in DP, well actually it's easier.
Friend: Now we check in a similar way?
Friend: We check if(12>10) so 12's count gets incremented? Friend: So let me clear this up, when 10 was alone LIS is 1 and now that 12 is added and we find {10, 12} could be LIS since 12>10 and so we add count of 10's to 12's count and add 1 to include the number itself.
Now let us consider 32, increment
Me: We check all numbers before 32 to see if they can be added to form a sequence with it, so increment j, continue filling in the boxes!
And similarly the rest of the array is traversed and the array becomes,
Since the highest is 6, which gives the longest increasing subsequence, the video of the above traversal is linked here(different example). Let's have a look at the code snippet of the same below. As we have learned,
After that, we find the maximum of the count array and print it, full code snippet is here and a look-alike problem just with a pair of numbers. More to come
Points to remember
Other resources
Problems lists from various sites
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论