title: Cost function of a dynamic solution to the "longest increasing subsequence" problem
body: <p>So I have a pretty simple dynamic programming solution to the &quot;longest increasing subsequence&quot; problem (find the longest subsequence of increasing elements in a given sequence, for instance for [1, 7, 2, 6, 4] it would be [1, 2, 4]), which can also find the actual subsequence (as opposed to just lenght):</p>
  <pre><code>sequence = [1, 8, 6, 4, 9, 8, 3, 5, 2, 7, 1, 9, 5, 7]
  listofincreasing = [[] for _ in range(len(sequence))]
  listofincreasing[0].append(sequence[0])
  
  for right in range(1, len(sequence)):
      for left in range(right):
          if (sequence[left] &lt; sequence[right]) and (len(listofincreasing[right]) &lt; len(listofincreasing[left])):
              listofincreasing[right] = [] + listofincreasing[left]
      listofincreasing[right].append(sequence[right])
  
  print(max(listofincreasing, key=len))
  </code></pre>
  <p>These sort of brainteasers are pretty manageable for me, but I don't really know the hard theory behind this. My question is this: How would I go about creating a cost function that would formally describe &quot;how I am filling the list', so to speak? Could someone show me how to approach these problems on this example? Thanks in advance.</p>
  <p>Edit - some people asked for a clarification. In the most succint way possible, I would need to create a mathematic function in the the exact same way as it is created here: <a href="https://medium.com/@pp7954296/change-making-problem-dynamic-method-4954a446a511" rel="nofollow noreferrer">https://medium.com/@pp7954296/change-making-problem-dynamic-method-4954a446a511</a> in the &quot;formula to solve coin change using dynamic method:&quot; section, but not for the change making problem but for my solution of the longest increasing subsequence problem</p>