Press "Enter" to skip to content

Posts tagged as “dp”

花花酱 LeetCode 730. Count Different Palindromic Subsequences

Problem:

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo 10^9 + 7.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences A_1, A_2, ... and B_1, B_2, ... are different if there is some i for which A_i != B_i.

Example 1:

Input: 
S = 'bccb'
Output: 6
Explanation: 
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input: 
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
Output: 104860361
Explanation: 
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

Note:

 

  • The length of S will be in the range [1, 1000].
  • Each character S[i] will be in the set {'a', 'b', 'c', 'd'}.



Idea:

DP

 

Solution 1: Recursion with memoization

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

C++

Python

Java

Solution 2: DP

C++

Pyhton

Related Problems:

花花酱 LeetCode 321. Create Maximum Number

Problem:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]



题目大意:给你两个数字数组和k,返回从两个数组中选取k个数字能够组成的最大值。

Idea: Greedy + DP

Solution:

Time complexity: O(k * (n1+n2)^2)

Space complexity: O(n1+n2)

C++

Java

花花酱 LeetCode 724. Find Pivot Index

Problem:

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Example 2:

Note:

 

  • The length of nums will be in the range [0, 10000].
  • Each element nums[i] will be an integer in the range [-1000, 1000].



Idea:

DP

Solution:

C++

 

Java

 

Python

 

 

花花酱 LeetCode 91. Decode Ways

题目大意:

给你一个加密的数字字符串,问你一共有多少种不同的解密方式。

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1

‘B’ -> 2

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

 



Idea:

Dynamic Programming

Solution:

C++

Time complexity: O(n^2)

Space complexity: O(n^2)

 

C++

Time complexity: O(n)

Space complexity: O(n)

 

 

 

C++

Time complexity: O(n)

Space complexity: O(1)

 

Related Problems:

花花酱 LeetCode 72. Edit Distance

Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Idea:

Dynamic Programming

Solution:

Recursive

Iterative