{"id":285,"date":"2020-12-20T18:45:06","date_gmt":"2020-12-20T18:45:06","guid":{"rendered":"https:\/\/www.canosielabs.com\/blog\/?p=285"},"modified":"2020-12-21T18:09:05","modified_gmt":"2020-12-21T18:09:05","slug":"unique-paths","status":"publish","type":"post","link":"https:\/\/www.canosielabs.com\/blog\/unique-paths\/","title":{"rendered":"Unique Paths"},"content":{"rendered":"\n

Today, we’ll talk about the unique paths problem<\/a>. <\/p>\n\n\n\n

A robot is located at the top-left corner of a m x n<\/code> grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).<\/strong><\/p>\n\n\n\n

How many possible unique paths are there?<\/strong><\/p>\n\n\n\n

Since at any given position, the user can make 2 decisions, the trivial DFS solution will be O(2n<\/sup>) Let’s study some interesting facts that might lead us to a better solution. <\/p>\n\n\n\n

Fact 1:<\/strong> Since the robot can only move right or down, all coordinates where m = 0 OR n = 0 are 1. This is because there is only one way to reach those coordinates because they are on the edges of the grid.<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Fact 2<\/strong>: The number of unique paths to a position (m, n) is the number of unique paths to position (m – 1, n) plus the number of uniquely paths from position (m, n – 1). This is (m – 1, n) and (m, n – 1) are the only two grid positions where move in one step to (m, n).<\/p>\n\n\n\n

This immediately looks like a dynamic programing problem since we have our base case and optimal substructure properties filled.<\/p>\n\n\n\n

Overlapping Sub-problem<\/strong> \u2013 Yes. We can see that as we break the problem down, we are repeating the subproblems multiple times. To get an idea why, consider the tree of function invocations.<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

Optimal Substructure<\/strong>\u00a0\u2013 Yes. The optimal solution to f(n) must include the optimal solution to f(m-1, n) and f(m, n-1) otherwise the solution will not be optimal.<\/p>\n\n\n\n

Base Case <\/strong>– The base case is when n=0 or m=0 (as mentioned in fact 1).<\/p>\n\n\n\n

DP Table<\/h2>\n\n\n\n

In this problem, our table will be a 2D array of size m by n. Each position (m, n) will hold the maximum number of unique paths to get to (m, n).<\/p>\n\n\n\n

Tabulation<\/h2>\n\n\n\n
class Solution {\n    public int uniquePaths(int m, int n) {\n    \t\n    \tif (m == 1 && n == 1) {\n    \t\treturn 1;\n    \t}\n        \n        int[][] memo = new int[m][n];\n        \n        for(int i=0; i<m; i++){\n            memo[i][0]=1;\n        }\n        \n        for(int i=0; i<n; i++){\n            memo[0][i]=1;\n        }\n        \n        for(int i=1; i<m; i++){\n          for(int j=1; j<n; j++){\n            memo[i][j] = memo[i][j-1] + memo[i-1][j];\n          }  \n        }\n        \n        return memo[m-1][n-1];\n    }\n}<\/code><\/pre>

\n\n\n\n
Conclusion<\/h2>\n\n\n\n
The unique paths is a fairly straight forward solution with the tabulation method so I’ll omit the recursive memoization method for now.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today, we’ll talk about the unique paths problem. A robot is located at the top-left corner of a m x n grid. The robot can only move…<\/p>\n","protected":false},"author":3,"featured_media":255,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[11],"tags":[10,7],"class_list":["post-285","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-coding-questions","tag-coding-questions","tag-interview-prep"],"_links":{"self":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/285","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/comments?post=285"}],"version-history":[{"count":6,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/285\/revisions"}],"predecessor-version":[{"id":300,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/285\/revisions\/300"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media\/255"}],"wp:attachment":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media?parent=285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/categories?post=285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/tags?post=285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}