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

LORY
14 min readMar 12, 2022

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 .

The process is to check the result of every combination of input<i,j> and make use the result of previous combination <i-1,j-1>,<i,j-1>or<i-1,j> which calculated earlier , Which end up with O(N²) time complexity.

Sample problems

583. Delete Operation for Two Strings

Thought process. To start solve the problem. you can ask yourself , could it be solved when word1 length=1 and word2=1, then how about word1 length =1 and word2 length=2,3,4… ? then let word1 length=2, word2 length=1,2,3 … by keep increasing the problem scope, you can identify what need to be cached in earlier inputs , which could be reused in solving current scope of inputs .And also, we need to compare every char in word1 (char1) with every char in word2 (char2) . when char1=char2 what will be the result ? and how about char1≠char2 ? after address these questions , now the pattern is clear .

def minDistance(self, word1: str, word2: str) ->…

--

--

LORY

A channel which focusing on developer growth and self improvement