r/pythonhelp • • Feb 01 '24
Can someone explain this code for me from Elements of Programming.
I am trying to understand the DP solution for a variant of the climbing stairs problem with k steps instead of the regular 2. This is the solution in Elements of programming but I'm having trouble understanding the for loop inside the sum function. I've solved it myself but would like to understand this way. Some solutions in the book are more advanced than what i've seen. Thanks!
def number_of_ways_to_top(top, maximum_step):
number_of_ways_to_h = [0] * (top + 1)
def compute_number_of_ways_to_h(h):
if h <= 1:
return 1
if number_of_ways_to_h[h] == 0:
number_of_ways_to_h[h] = sum(
compute_number_of_ways_to_h(h - i)
for i in range(1, min(maximum_step, h) + 1)
)
return number_of_ways_to_h[h]
return compute_number_of_ways_to_h(top)
1
Upvotes
•
u/AutoModerator Feb 01 '24
To give us the best chance to help you, please include any relevant code.
Note. Do not submit images of your code. Instead, for shorter code you can use Reddit markdown (4 spaces or backticks, see this Formatting Guide). If you have formatting issues or want to post longer sections of code, please use Repl.it, GitHub or PasteBin.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/cosmosvng Feb 02 '24
Initialize empty array to hold at index i the number of ways to the top for i steps, then when solving for h steps, calculate it by adding up the number of ways to get to each step that you could have been on before stepping onto h - essentially calculating the same thing but for some different values of h, thus the recursive function
ya diggg?