Press "Enter" to skip to content

Posts published in “Dynamic Programming”

花花酱 LeetCode 1335. Minimum Difficulty of a Job Schedule

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

Example 4:

Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:

Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

Constraints:

  • 1 <= jobDifficulty.length <= 300
  • 0 <= jobDifficulty[i] <= 1000
  • 1 <= d <= 10

Solution: DP

dp[i][k] := min difficulties to schedule jobs 1~i in k days.

Schedule 1 ~ j in k – 1 days and schedule j + 1 ~ i in 1 day.

Init: dp[0][0] = 0
Transition: dp[i][k] := min(dp[j][k -1] + max(jobs[j + 1 ~ i]), k – 1 <= j < i
Answer: dp[n][d]

Time complexity: O(n^2*d)
Space complexity: O(n)

C++

花花酱 LeetCode 42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution 1: Brute Force

r[i] = min(max(h[0:i+1]), max(h[i:n]))
ans = sum(r[i])

Time complexity: O(n^2)
Space complexity: O(1)

C++

Solution 2: DP

l[i] := max(h[0:i+1])
r[i] := max(h[i:n])
ans = sum(min(l[i], r[i]) – h[i])

Time complexity: O(n)
Space complexity: O(n)

C++

Solution 3: Two Pointers

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers

You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is located at coordinate (0,1), the letter P is located at coordinate (2,3) and the letter Z is located at coordinate (4,1).

Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates (x1,y1) and (x2,y2) is |x1 – x2| + |y1 – y2|

Note that the initial positions of your two fingers are considered free so don’t count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example 1:

Input: word = "CAKE"
Output: 3
Explanation: 
Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Example 2:

Input: word = "HAPPY"
Output: 6
Explanation: 
Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

Example 3:

Input: word = "NEW"
Output: 3

Example 4:

Input: word = "YEAR"
Output: 7

Constraints:

  • 2 <= word.length <= 300
  • Each word[i] is an English uppercase letter.

Solution: DP

Top down: O(n*27^2)

C++

C++

C++

花花酱 LeetCode 1314. Matrix Block Sum

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, K <= 100
  • 1 <= mat[i][j] <= 100

Solution: 2D range query

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

花花酱 LeetCode 1310. XOR Queries of a Subarray

Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the XOR of elements from Li to Ri (that is, arr[Lixor arr[Li+1xor ... xor arr[Ri] ). Return an array containing the result for the given queries.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 10^9
  • 1 <= queries.length <= 3 * 10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] <= queries[i][1] < arr.length

Solution: Prefix Sum

Time complexity: O(n) + O(q)
Space complexity: O(n)

C++

tby