Commit506ba68

authored

Create 1269-number-of-ways-to-stay-in-the-same-place-after-some-steps.js

Solved number-of-ways-to-stay-in-the-same-place-after-some-steps

1 parent0a2d881 commit506ba68Copy full SHA for 506ba68

File tree

+29

-0

lines changed

+29

-0

lines changed

Lines changed: 29 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,29 @@`
	`1`	`+/**`
	`2`	`+ * DP \| Recursion`
	`3`	`+ * Time O(n^2) \| Space O(n^2)`
	`4`	`+ * https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/`
	`5`	`+ *@param {number} steps`
	`6`	`+ *@param {number} arrLen`
	`7`	`+ *@return {number}`
	`8`	`+ */`
	`9`	`+varnumWays=function(steps,arrLen){`
	`10`	`+`
	`11`	`+constcache=newMap();`
	`12`	`+constmod=10**9+7;`
	`13`	`+`
	`14`	`+constdfs=(i,leftSteps)=>{`
	`15`	`+`
	`16`	+consthash=`${i},${leftSteps}`;
	`17`	`+`
	`18`	`+if(cache.has(hash))returncache.get(hash);`
	`19`	`+if(i<0\|\|i===arrLen)return0;`
	`20`	`+if(i===0&&leftSteps===0)return1;`
	`21`	`+if(leftSteps===0)return0;`
	`22`	`+`
	`23`	`+constres=(dfs(i-1,leftSteps-1)+dfs(i+1,leftSteps-1)+dfs(i,leftSteps-1))%mod;`
	`24`	`+cache.set(hash,res);`
	`25`	`+returnres;`
	`26`	`+}`
	`27`	`+`
	`28`	`+returndfs(0,steps);`
	`29`	`+};`

Comments

(0)