Dynamic Programming

[Leetcode] Trapping Rain Water

While the concept is two pointers converging from opposite sides, the implementation is more in a dp form.

Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how…

[Leetcode] Unique Paths

Matrix problem that leverages dp.

Description

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1])…

[Leetcode] Partition Equal Subset Sum

Store boolean inside dp[].

Description

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

[Leetcode Pattern] Dynamic Programming

A cheet sheet of dp problems in leetcode.

Determinate factors…

[Leetcode] Decode Ways

Write the rule of int carry into dp.

Description

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

[Leetcode] Word Break

Think about how to break the target into smaller pieces, choose a data structure to efficiently store the info of the addressed pieces and call that info to use on further breaking target.

Description

[Leetcode] Counting Bits

Dynamic programming is all about finding pattern.

Description

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

[Leetcode] Longest Increasing Subsequence

Maintain the enlarging maximum along the dp array.

Description

Given an integer array nums, return the length of the longest strictly increasing subsequence.