# Posts tagged as “dp”

You are given two sorted arrays of distinct integers nums1 and nums2.

validpath is defined as follows:

• Choose array nums1 or nums2 to traverse (from index-0).
• Traverse the current array from left to right.
• If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].


Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].


Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].


Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61


Constraints:

• 1 <= nums1.length <= 10^5
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^7
• nums1 and nums2 are strictly increasing.

## Solution: Two Pointers + DP

Since numbers are strictly increasing, we can always traverse the smaller one using two pointers.
Traversing ([2,4,5,8,10], [4,6,8,10])
will be like [2, 4/4, 5, 6, 8, 10/10]
It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.
dp1[i] := max path sum ends with nums1[i-1]
dp2[j] := max path sum ends with nums2[j-1]
if nums[i -1] == nums[j – 1]:
dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]
i += 1, j += 1
else if nums[i – 1] < nums[j – 1]:
dp[i] = dp[i-1] + nums[i -1]
i += 1
else if nums[j – 1] < nums[i – 1]:
dp[j] = dp[j-1] + nums[j -1]
j += 1
return max(dp1[-1], dp2[-1])

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

## python3

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.


Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.


Example 4:

Input: s = "000"
Output: 0


Constraints:

• s[i] == '0' or s[i] == '1'
• 1 <= s.length <= 10^5

## Solution: DP/ Prefix Sum

dp[i] := # of all 1 subarrays end with s[i].
dp[i] = dp[i-1] if s[i] == ‘1‘ else 0
ans = sum(dp)
s=1101
dp[0] = 1 // 1
dp[1] = 2 // 11, *1
dp[2] = 0 // None
dp[3] = 1 // ***1
ans = 1 + 2 + 1 = 5

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

## C++

dp[i] only depends on dp[i-1], we can reduce the space complexity to O(1)

## Python3

Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding '1' after single characters.

Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.

Find the minimum length of the run-length encoded version of s after deleting at most k characters.

Example 1:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

Example 2:

Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.


Example 3:

Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.


Constraints:

• 1 <= s.length <= 100
• 0 <= k <= s.length
• s contains only lowercase English letters.

## Solution 0: Brute Force DFS (TLE)

Time complexity: O(C(n,k))
Space complexity: O(k)

## Solution1: DP

State:
i: the start index of the substring
last: last char
len: run-length
k: # of chars that can be deleted.

base case:
1. k < 0: return inf # invalid
2. i >= s.length(): return 0 # done

Transition:
1. if s[i] == last: return carry + dp(i + 1, last, len + 1, k)

2. if s[i] != last:
return min(1 + dp(i + 1, s[i], 1, k, # start a new group with s[i]
dp(i + 1, last, len, k -1) # delete / skip s[i], keep it as is.

Time complexity: O(n^3*26)
Space complexity: O(n^3*26)

## State compression

dp[i][k] := min len of s[i:] encoded by deleting at most k charchters.

dp[i][k] = min(dp[i+1][k-1] # delete s[i]
encode_len(s[i~j] == s[i]) + dp(j+1, k – sum(s[i~j])) for j in range(i, n)) # keep

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

## Python3

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.


Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.


Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16


Example 4:

Input: arr = [100,100,99,99]
Output: 4


Example 5:

Input: arr = [7]
Output: 1


Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100

## Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i][0] := # end with arr[i] has even sum
dp[i][1] := # end with arr[i] has even sum

if arr[i] is even:

dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]

else:

dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1

ans = sum(dp[i][1])

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

## Python3

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile.  On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).


Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0).
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).

Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.


Constraints:

• 1 <= n <= 10^5

## Solution: Recursion w/ Memoization / DP

Let win(n) denotes whether the current play will win or not.
Try all possible square numbers and see whether the other player will lose or not.
win(n) = any(win(n – i*i) == False) ? True : False
base case: win(0) = False

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

## Python3

Mission News Theme by Compete Themes.