Return to Answer

I incorporated suggestions that @Graipher made in his answer. This is the improved function that resulted from it.
###Solution

history = {}
def cut_log(p, n):
 global history
 ln = len(p)
 if id(p) not in history:
 p = p + [0]*max(n - ln, 0)
 for i in range(2, max(n+1, ln)):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 history[id(p)] = p
 else:
 p = history[id(p)]
 ln = len(p)
 if n+1 > ln:
 p = p + [0]*max(n - ln, 0)
 for i in range(ln, n+1):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

I wasn't memoising the function, and I added that for increased performance.

I incorporated suggestions that @Graipher made in his answer. This is the improved function that resulted from it.

Solution

history = {}
def cut_log(p, n):
 global history
 ln = len(p)
 if id(p) not in history:
 p = p + [0]*max(n - ln, 0)
 for i in range(2, max(n+1, ln)):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 history[id(p)] = p
 else:
 p = history[id(p)]
 ln = len(p)
 if n+1 > ln:
 p = p + [0]*max(n - ln, 0)
 for i in range(ln, n+1):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

I wasn't memoising the function, and I added that for increased performance.

I incorporated suggestions that @Graipher made in his answer. This is the improved function that resulted from it.
###Solution

history = {}
def cut_log(p, n):
 global history
 ln = len(p)
 if id(p) not in history:
 p = p + [0]*max(n - ln, 0)
 for i in range(2, max(n+1, ln)):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 history[id(p)] = p
 else:
 p = history[id(p)]
 ln = len(p)
 if n+1 > ln:
 p = p + [0]*max(n - ln, 0)
 for i in range(ln, n+1):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

I incorporated suggestions that @Graipher made in his answer. This is the improved function that resulted from it.
###Solution

history = {}
def cut_log(p, n):
 global history
 ln = len(p)
 if id(p) not in history:
 p = p + [0]*max(n - ln, 0)
 for i in range(2, max(n+1, ln)):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 history[id(p)] = p
 else:
 p = history[id(p)]
 ln = len(p)
 if n+1 > ln:
 p = p + [0]*max(n - ln, 0)
 for i in range(ln, n+1):
 p[i] = max(p[i-k] + p[k] for k in range((i//2)+1))
 return p[n]

I wasn't memoising the function, and I added that for increased performance.