log(n) (space) and o(n) (time) speedy solution for Golden Pyramid by DiZ - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

log(n) (space) and o(n) (time) solution in Speedy category for Golden Pyramid by DiZ

def count_gold(pyramid):
    m = [0]*(len(pyramid)+1)
    for line in reversed(pyramid):
        m = [v + max(m[k:k+2]) for k,v in enumerate(line)]
    return m[0]

May 9, 2014

Comments:

xiongbiao on May 23, 2014, 7:52 a.m.
Readable

redteer on June 20, 2014, 1:13 a.m.
log(n)?I'm not sure.Can you explain?Space complexity is O(log(n)) obviously, but I think this algorithm is O(n) in time complxity.Your algorithm calculated/touched every element in pyramid and did one time add and compare operation for every element.If I'm wrong pls tell me.Thank you.^_^

DiZ on June 20, 2014, 10:28 a.m.
You're absolutely right, this algorithm is linear in time with respect to the number of lines.

Look up in the Dict()

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.