Commit21d73b6

authored

algorithm: unique paths (TheAlgorithms#1211)

* dp problem* update Directory.md* suggested changes

1 parent16fa774 commit21d73b6Copy full SHA for 21d73b6

File tree

+53

-0

lines changed

+53

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -105,6 +105,7 @@`
`105`	`105`	`*[RodCutting](Dynamic-Programming/RodCutting.js)`
`106`	`106`	`*[Shuf](Dynamic-Programming/Shuf.js)`
`107`	`107`	`*[SieveOfEratosthenes](Dynamic-Programming/SieveOfEratosthenes.js)`
	`108`	`+*[UniquePaths](Dynamic-Programming/UniquePaths.js)`
`108`	`109`	`*Sliding-Window`
`109`	`110`	`*[LongestSubstringWithoutRepeatingCharacters](Dynamic-Programming/Sliding-Window/LongestSubstringWithoutRepeatingCharacters.js)`
`110`	`111`	`*[PermutationinString](Dynamic-Programming/Sliding-Window/PermutationinString.js)`

Lines changed: 41 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,41 @@`
	`1`	`+`
	`2`	`+/*`
	`3`	`+ *`
	`4`	`+ * Unique Paths`
	`5`	`+ *`
	`6`	+ * There is a robot on an `m x n` grid.
	`7`	`+ * The robot is initially located at the top-left corner.`
	`8`	`+ * The robot tries to move to the bottom-right corner.`
	`9`	`+ * The robot can only move either down or right at any point in time.`
	`10`	`+ *`
	`11`	+ * Given the two integers `m` and `n`,
	`12`	`+ * return the number of possible unique paths that the robot can take to reach the bottom-right corner.`
	`13`	`+ * More info: https://leetcode.com/problems/unique-paths/`
	`14`	`+ */`
	`15`	`+`
	`16`	`+/*`
	`17`	`+ *@param {number} m`
	`18`	`+ *@param {number} n`
	`19`	`+ *@return {number}`
	`20`	`+ */`
	`21`	`+`
	`22`	`+constuniquePaths=(m,n)=>{`
	`23`	`+// only one way to reach end`
	`24`	`+if(m===1\|\|n===1)return1`
	`25`	`+`
	`26`	`+// build a linear grid of size m`
	`27`	`+// base case, position 1 has only 1 move`
	`28`	`+constpaths=newArray(m).fill(1)`
	`29`	`+`
	`30`	`+for(leti=1;i<n;i++){`
	`31`	`+for(letj=1;j<m;j++){`
	`32`	`+// paths[j] in RHS represents the cell value stored above the current cell`
	`33`	`+// paths[j-1] in RHS represents the cell value stored to the left of the current cell`
	`34`	`+// paths [j] on the LHS represents the number of distinct pathways to the cell (i,j)`
	`35`	`+paths[j]=paths[j-1]+paths[j]`
	`36`	`+}`
	`37`	`+}`
	`38`	`+returnpaths[m-1]`
	`39`	`+}`
	`40`	`+`
	`41`	`+export{uniquePaths}`

Lines changed: 11 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,11 @@`
	`1`	`+import{uniquePaths}from'../UniquePaths'`
	`2`	`+`
	`3`	`+describe('Unique Paths',()=>{`
	`4`	`+it('should return 28 when m is 3 and n is 7',()=>{`
	`5`	`+expect(uniquePaths(3,7)).toBe(28)`
	`6`	`+})`
	`7`	`+`
	`8`	`+it('should return 48620 when m is 10 and n is 10',()=>{`
	`9`	`+expect(uniquePaths(10,10)).toBe(48620)`
	`10`	`+})`
	`11`	`+})`

Comments

(0)