{"id":25956,"date":"2017-10-25T22:07:17","date_gmt":"2017-10-25T16:37:17","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25956"},"modified":"2017-10-25T22:07:17","modified_gmt":"2017-10-25T16:37:17","slug":"java-programming-min-cost-path","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-min-cost-path\/","title":{"rendered":"Java Programming &#8211; Min Cost Path"},"content":{"rendered":"<p>Given 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. <span id=\"more-14943\"><\/span>Total cost of a path to reach (m, n) is 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.<\/p>\n<p>For example, in the following figure, what is the minimum cost path to (2, 2)?<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-25961\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Min-Cost.png\" alt=\"Min Cost Path\" width=\"279\" height=\"242\" \/><\/p>\n<p>The path with minimum cost is highlighted in the following figure. The path is (0, 0) \u2013> (0, 1) \u2013> (1, 2) \u2013> (2, 2). The cost of the path is 8 (1 + 2 + 2 + 3).<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-25964\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Min-Cost-Path.png\" alt=\"Min Cost Path\" width=\"279\" height=\"242\" \/><\/p>\n<ul>\n<li><strong>Optimal Substructure<\/strong><br \/>\nThe path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or (m, n-1). So minimum cost to reach (m, n) can be written as \u201cminimum of the 3 cells plus cost[m][n]\u201d.<\/li>\n<\/ul>\n<p>minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]\n<ul>\n<li><strong>Overlapping Subproblems<\/strong><br \/>\nFollowing is simple recursive implementation of the MCP (Minimum Cost Path) problem. The implementation simply follows the recursive structure mentioned above.<\/li>\n<\/ul>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F*%20A%20Naive%20recursive%20implementation%20of%20MCP(Minimum%20Cost%20Path)%20problem%20*%2F%0A%23include%3Cstdio.h%3E%0A%23include%3Climits.h%3E%0A%23define%20R%203%0A%23define%20C%203%0A%20%0Aint%20min(int%20x%2C%20int%20y%2C%20int%20z)%3B%0A%20%0A%2F*%20Returns%20cost%20of%20minimum%20cost%20path%20from%20(0%2C0)%20to%20(m%2C%20n)%20in%20mat%5BR%5D%5BC%5D*%2F%0Aint%20minCost(int%20cost%5BR%5D%5BC%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20if%20(n%20%3C%200%20%7C%7C%20m%20%3C%200)%0A%20%20%20%20%20%20return%20INT_MAX%3B%0A%20%20%20else%20if%20(m%20%3D%3D%200%20%26%26%20n%20%3D%3D%200)%0A%20%20%20%20%20%20return%20cost%5Bm%5D%5Bn%5D%3B%0A%20%20%20else%0A%20%20%20%20%20%20return%20cost%5Bm%5D%5Bn%5D%20%2B%20min(%20minCost(cost%2C%20m-1%2C%20n-1)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20minCost(cost%2C%20m-1%2C%20n)%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20minCost(cost%2C%20m%2C%20n-1)%20)%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20that%20returns%20minimum%20of%203%20integers%20*%2F%0Aint%20min(int%20x%2C%20int%20y%2C%20int%20z)%0A%7B%0A%20%20%20if%20(x%20%3C%20y)%0A%20%20%20%20%20%20return%20(x%20%3C%20z)%3F%20x%20%3A%20z%3B%0A%20%20%20else%0A%20%20%20%20%20%20return%20(y%20%3C%20z)%3F%20y%20%3A%20z%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20int%20cost%5BR%5D%5BC%5D%20%3D%20%7B%20%7B1%2C%202%2C%203%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B4%2C%208%2C%202%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%205%2C%203%7D%20%7D%3B%0A%20%20%20printf(%22%20%25d%20%22%2C%20minCost(cost%2C%202%2C%202))%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>It should be noted that the above function computes the same subproblems again and again. See the following recursion tree, there are many nodes which appear more than once. Time complexity of this naive recursive solution is exponential and it is terribly slow.<\/p>\n[ad type=\u201dbanner\u201d]\n<pre>mC refers to minCost()\r\n                                    mC(2, 2)\r\n                          \/            |           \\\r\n                         \/             |            \\             \r\n                 mC(1, 1)           mC(1, 2)             mC(2, 1)\r\n              \/     |     \\       \/     |     \\           \/     |     \\ \r\n             \/      |      \\     \/      |      \\         \/      |       \\\r\n       mC(0,0) mC(0,1) mC(1,0) mC(0,1) mC(0,2) mC(1,1) mC(1,0) mC(1,1) mC(2,0) \r\n<\/pre>\n<p>So the MCP problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array tc[][] in bottom up manner.<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F*%20Java%20program%20for%20Dynamic%20Programming%20implementation%0A%20%20%20of%20Min%20Cost%20Path%20problem%20*%2F%0Aimport%20java.util.*%3B%0A%20%0Aclass%20MinimumCostPath%0A%7B%0A%20%20%20%20%2F*%20A%20utility%20function%20that%20returns%20minimum%20of%203%20integers%20*%2F%0A%20%20%20%20private%20static%20int%20min(int%20x%2C%20int%20y%2C%20int%20z)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(x%20%3C%20y)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20(x%20%3C%20z)%3F%20x%20%3A%20z%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20(y%20%3C%20z)%3F%20y%20%3A%20z%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20private%20static%20int%20minCost(int%20cost%5B%5D%5B%5D%2C%20int%20m%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20i%2C%20j%3B%0A%20%20%20%20%20%20%20%20int%20tc%5B%5D%5B%5D%3Dnew%20int%5Bm%2B1%5D%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20tc%5B0%5D%5B0%5D%20%3D%20cost%5B0%5D%5B0%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Initialize%20first%20column%20of%20total%20cost(tc)%20array%20*%2F%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%3D%20m%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20tc%5Bi%5D%5B0%5D%20%3D%20tc%5Bi-1%5D%5B0%5D%20%2B%20cost%5Bi%5D%5B0%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Initialize%20first%20row%20of%20tc%20array%20*%2F%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%201%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20tc%5B0%5D%5Bj%5D%20%3D%20tc%5B0%5D%5Bj-1%5D%20%2B%20cost%5B0%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Construct%20rest%20of%20the%20tc%20array%20*%2F%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%3D%20m%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%20%3D%201%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tc%5Bi%5D%5Bj%5D%20%3D%20min(tc%5Bi-1%5D%5Bj-1%5D%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tc%5Bi-1%5D%5Bj%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20tc%5Bi%5D%5Bj-1%5D)%20%2B%20cost%5Bi%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20return%20tc%5Bm%5D%5Bn%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20cost%5B%5D%5B%5D%3D%20%7B%7B1%2C%202%2C%203%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B4%2C%208%2C%202%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B1%2C%205%2C%203%7D%7D%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22minimum%20cost%20to%20reach%20(2%2C2)%20%3D%20%22%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20minCost(cost%2C2%2C2))%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>8<\/pre>\n<p>Time Complexity of the DP implementation is O(mn) which is much better than Naive Recursive implementation.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Java Programming &#8211; Min Cost Path &#8211; Dynamic Programming the MCP problem has both properties of a dynamic programming problem. Like other typical DP problems,<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,2139],"tags":[76394,72848,72840,72846,72987,72985,72843,72854,72844,72850,76404,76396,76398,72839,76405,76401,76400,76399,76395,76393,76406,76397,76403,72852,72855,72853,72851],"class_list":["post-25956","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-java","tag-dynamic-programming-and-min-cost-path","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-java","tag-dynamic-programming-java","tag-dynamic-programming-problems","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-find-all-paths-in-a-matrix","tag-find-minimum-cost-path","tag-finding-path-in-minimum-cost-path-algo-using-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-maximum-sum-in-path-through-a-2d-array","tag-maximum-sum-path-in-a-matrix","tag-min-cost-path","tag-minimum-cost-path-dp-example","tag-minimum-cost-path-dynamic-programming","tag-minimum-cost-path-in-java","tag-minimum-cost-path-java","tag-minimum-cost-path-problem","tag-minimum-cost-path-problem-java","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25956","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25956"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25956\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25956"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25956"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25956"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}