Make it recursive, Optimze with Dict or array.
- Try Brute force
- Look for optimization
- Is there any repetation
- Look for a recursion
- Use dict or array to store values
1. Longest Non Decreasing Sub Sequence
1. Create a Temporary array
2. Iterate the input and compare with elements in the temp array
3. if input<curr
replace curr = input
break
if input >= curr:
next element
end of inner loop
add input to temp array if not already added
4.return length of temp array
def longest_nondecreasing_subsequence_length(A: List[int]) -> int:
result = list()
for n in A:
add = True
for i in range(len(result)):
if n< result[i]:
result[i] = n
add = False
break
if add:
result.append(n)
return len(result)
2. Combination of stairs
How many possible ways to clib a stair
#maxstep: how many steps in one move,eg 3 means, 1 or 2 or 3 steps in a move
#total stair: 5
1. yes its recursion withe memoization
2. total = onestep then func(stairs-1) + twostep then func(stairs-2) + three step then func(stairs-3)
Things to note:
* no Need to use set
* no need to keep all the combination just number is enough
def number_of_ways_to_top(top: int, maximum_step: int) -> int:
myd = dict()
myd[1] =1
myd[0] = 1 # yes its one
def generate (stair,steps):
#print(stair)
if(stair<0):
return 0
if stair in myd:
return myd[stair]
total = 0
for step in range(1,steps+1):
total+= generate(stair-step,steps)
myd[stair] = total
return total
return (generate(top,maximum_step))
#return generate(4,2)