After solved 1000 leetcode medium level I found these patterns — Dynamic Programming

TL;DR;

Continue with Leetcode patterns . here is another classic algorithm — DP .

This is my progress so far (from 2021 till now).

Now I am having a break and write down the patterns i have learned so far .

So In this article i will list all the high ranking DP leetcode problems and explain the algorithm pattern of Dynamic programming .

First thing first , I don’t like this algorithm to be honest because it is not very likely be used in realworld projects, the code usually hard to explain itself without enough comments (we need maintein these comments). I will consider solution with DFS+cache . i will explain why and how later .

Idea

Try solve the problem with smaller inputs, with brute force or backtracking , identify what can be “cached” during sub-problem solving.

Bottom up

This is classic DP pattern .

def solve(input):
  results = [[]] * len(input)
  for i in index in inputs:
      for j in index before i:
          if condition <i,j>:
              result[i][j] = best of \
             (result[i][j], \
              result[i-1][j-1]+1, \
              result[i][j-1], \
              result[i-1][j])
  return results

Input could be matrix, string or array .