Applying DP on structures other than arrays, like Trees or Digits.
DP doesn't always iterate i from 0 to N. The transition can happen over any Directed Acyclic Graph. A very common pattern is Tree DP.
In Tree DP, we use a post-order traversal (DFS). We recursively solve for all children of a node first, and then the parent node combines the answers of its children to form its own answer. State usually looks like dp[node][state].
def dfs(node, parent):
# dp[node][0] = max if we DON'T include node
# dp[node][1] = max if we DO include node
dp_0 = 0
dp_1 = values[node]
for child in adj[node]:
if child != parent:
child_0, child_1 = dfs(child, node)
# If we don't include node, we can choose best of child
dp_0 += max(child_0, child_1)
# If we do include node, we MUST NOT include child
dp_1 += child_0
return dp_0, dp_1