Press "Enter" to skip to content

Posts published in “Dynamic Programming”

花花酱 LeetCode 410. Split Array Largest Sum

Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

 

Solution: DP

Time complexity: O(n^2*m)

Space complexity: O(n*m)

C++ / Recursion + Memorization

C++ / DP

Solution: Binary Search

Time complexity: O(log(sum(nums))*n)

Space complexity: O(1)

 

花花酱 LeetCode 845. Longest Mountain in Array

Problem

题目大意:找出最长的山形子数组。

https://leetcode.com/problems/longest-mountain-in-array/description/

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

  • B.length >= 3
  • There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

 

Note:

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

Solution: DP

Three passes

Time complexity: O(n)

Space complexity: O(n)

C++

One pass

Time complexity: O(n)

Space complexity: O(1)

 

花花酱 LeetCode 576. Out of Boundary Paths

Problem

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

  1. Once you move the ball out of boundary, you cannot move it back.
  2. The length and height of the grid is in range [1,50].
  3. N is in range [0,50].

Solution

Time complexity: O(m*n + N * m * n)

Space complexity: O(N*m*n) -> O(m*n)

C++

Recursion with memorization

no loops

 

Related Problems

花花酱 LeetCode 516. Longest Palindromic Subsequence

Problem

题目大意:找出最长回文子序列的长度。

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

Time complexity: O(n^2)

Space complexity: O(n)

C++

Python3

C#

 

花花酱 LeetCode 329. Longest Increasing Path in a Matrix

Problem

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution1: DFS + Memorization

Time complexity: O(mn)

Space complexity: O(mn)

C++

Solution2: DP

DP

Time complexity: O(mn*log(mn))

Space complexity: O(mn)