Press "Enter" to skip to content

Posts published in “Dynamic Programming”

花花酱 LeetCode 664. Strange Printer

Problem:

There is a strange printer with the following two special requirements:

  1. The printer can only print a sequence of the same character each time.
  2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Example 2:

Hint: Length of the given string will not exceed 100.

Idea:

Dynamic programming



Time Complexity: 

O(n^3)

Space Complexity:

O(n^2)

Solution:

C++

Java

Python3

花花酱 LeetCode 304. Range Sum Query 2D – Immutable

 

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Problem:

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Note:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.
Idea:
Dynamic programming
Time complexity:
O(n^2)
sumRegion: O(1)
Solution:




 

花花酱 LeetCode 221. Maximal Square

Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

 

Idea:

Dynamic programming



Solution 0: O(n^5)

 

Solution 1: O(n^3)

Solution 2: O(n^2)

 

Solution 1:

 

Solution 2:

 

花花酱 LeetCode 673. Number of Longest Increasing Subsequence

https://leetcode.com/problems/number-of-longest-increasing-subsequence

Problem:

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Example 2:

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Idea:

Dynamic programming

Solution1:

Solution2:

Related Problems:

花花酱 LeetCode 300. Longest Increasing Subsequence

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Idea:

Dynamic Programming

Time Complexity:

O(n^2)

Solution 1:

Solution 2:

Related Problems: