Scribd
Upload
5 views

Dynamic Programming 1

Uploaded by

Muhiuddin Arif
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views

Dynamic Programming 1

Uploaded by

Muhiuddin Arif
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Solution:

def climbStairs(n: int) -> int:

if n == 1:
return 1
if n == 2:
return 2

prev1, prev2 = 2, 1

for i in range(3, n + 1):


current = prev1 + prev2
prev2 = prev1
prev1 = current

return prev1

Time Complexity:

● The loop runs from 3 to n, so the time complexity is O(n).

Space Complexity:
● We only need to store the last two computed values (prev1 and prev2), so the space
complexity is O(1).

Solution:
def maxProfit(prices):
max_profit = 0

for i in range(1, len(prices)):


if prices[i] > prices[i - 1]:
max_profit += prices[i] - prices[i - 1]

return max_profit

Time Complexity:

● O(n), where n is the length of the prices array. We loop through the list once, checking
each day.

Space Complexity:
● O(1). We only use a single integer max_profit to store the result, so the space
complexity is constant.

You might also like