Solution to LeetCode 1014 Best Sightseeing Pair.
LeetCode 1014
Best Sightseeing Pair (Medium) [link]
score = values[i] + values[j] + i - j = (values[i] + i) + (values[j] - j)
At each iteration, store the maximum score so far, as well as the maximum value of values[i] + i so far. The idea is that if values[i] + i is the maximum, then (values[i] + i) + (values[j] - j) is the maximum. In the implementation of the algorithm, the second max value would be chosen to get the max score for the first value.
Recurrence relation: dp[j] = max(dp[j], max_i(values[i]+i) + (values[j]-j))
class Solution(object):
def maxScoreSightseeingPair(self, values):
"""
:type values: List[int]
:rtype: int
"""
res = 0
pre = values[0] + 0
for j in range(1, len(values)):
res = max(res, pre + values[j] - j)
pre = max(pre, values[j] + j)
return res
LeetCode 1312
Minimum Insertion Steps to Make a String Palindrome (Hard) [link]
Define dp[i][j] as the minimum insertion steps to make string s[i:j] a palindrome. If s[i] == s[j], we need to consider s[i+1:j-1]. If s[i] != s[j], we need to consider adding s[i] to the end or adding s[j] to the front. Then we need to consider s[i+1:j] or s[i:j-1].
The recurrence relation is
If s[i] != s[j], then dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1.
If s[i] == s[j], then dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]).
Suppose the length of a string is span = j - i + 1, then j = span + i - 1.
Base cases: dp[i][j] = 0 if i >= j.
Time complexity O(n^2). Space complexity O(n^2).
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for span in range(2, n + 1):
for i in range(n - span + 1):
j = i + span - 1
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
if s[i] == s[j]:
dp[i][j] = min(dp[i][j], dp[i + 1][j - 1])
return dp[0][n - 1]
