Commit71d4c5c

authored

Merge pull requestneetcode-gh#1242 from aniruddhakj/patch-1

Updating 70.climbing_stairs.cpp

2 parents3d16d54 +cabffc3 commit71d4c5cCopy full SHA for 71d4c5c

File tree

+18

-2

lines changed

+18

-2

lines changed

Lines changed: 18 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -2,15 +2,31 @@`
`2`	`2`	`Climbing stairs, either 1 or 2 steps, distinct ways to reach top`
`3`	`3`	`Ex. n = 2 -> 2 (1 + 1, 2), n = 3 -> 3 (1 + 1 + 1, 1 + 2, 2 + 1)`
`4`	`4`
`5`		`-Recursion w/ memoization -> DP, why DP? Optimal substructure`
	`5`	`+Bottom-up DP`
`6`	`6`	`Recurrence relation: dp[i] = dp[i - 1] + dp[i - 2]`
`7`	`7`	`Reach ith step in 2 ways: 1) 1 step from i-1, 2) 2 steps from i-2`
`8`	`8`
`9`	`9`	`Time: O(n)`
`10`	`10`	`Space: O(1)`
`11`	`11`	`*/`
`12`	`12`
`13`		`-classSolution {`
	`13`	`+classSolutionBottomUp {`
	`14`	`+public:`
	`15`	`+//Fibonacci series : 'one' stores ways from [n-2]`
	`16`	`+//'two' stores ways from [n-1]`
	`17`	`+intclimbStairs(int n) {`
	`18`	`+int one =1, two =1;`
	`19`	`+for(int i =0; i < n -1; ++i){`
	`20`	`+int temp = one;`
	`21`	`+ one += two;`
	`22`	`+ two = temp;`
	`23`	`+ }`
	`24`	`+return one;`
	`25`	`+ }`
	`26`	`+};`
	`27`	`+`
	`28`	`+`
	`29`	`+classSolutionTopDown {`
`14`	`30`	`public:`
`15`	`31`	`intclimbStairs(int n) {`
`16`	`32`	`if (n ==1) {`

Comments

(0)