求起点为1终点为N的最小代价非严格递增子序列O(nlogn)解法

First, let's recap your existing O(n²) DP approach to make sure we're aligned:

• Define dp[i] as the minimum cost to reach position i with a valid non-decreasing subsequence starting at 1.
• Base case: dp[1] = 0 (since we start at position 1 with no cost incurred).
• Transition: For each i, dp[i] = min{ dp[j] + COST[i][j] } where j ≤ i and A[j] ≤ A[i].
• The final answer is dp[N].

The standard LIS O(n log n) method doesn't work here because it relies on uniform transition costs (like +1 for each step), but your COST[i][j] is arbitrary and varies with both i and j. Below are targeted optimization strategies depending on the properties of your COST matrix, plus a general approach using CDQ divide-and-conquer.

1. Optimization with Quadrilateral Inequality (QI) #

If your COST matrix satisfies the quadrilateral inequality, we can use a divide-and-conquer optimization to cut the time complexity down to O(n log n).

What's the Quadrilateral Inequality? #

For all i₁ ≤ i₂ and j₁ ≤ j₂, the following holds:

COST[i₁][j₁] + COST[i₂][j₂] ≤ COST[i₁][j₂] + COST[i₂][j₁]

Additionally, we need COST to be monotonic in its arguments (e.g., COST[i][j] ≤ COST[i'][j] for i ≤ i' and fixed j).

Implementation Outline #

This optimization leverages the fact that the optimal j for i is non-decreasing as i increases, so we don't need to check all possible js for each i:

def compute_dp(l, r, opt_l, opt_r):
    if l > r:
        return
    mid = (l + r) // 2
    best_j = opt_l
    min_cost = float('inf')
    # Only check j in [opt_l, min(opt_r, mid)] since optimal j is monotonic
    for j in range(opt_l, min(opt_r, mid) + 1):
        if A[j] <= A[mid] and dp[j] + COST[mid][j] < min_cost:
            min_cost = dp[j] + COST[mid][j]
            best_j = j
    dp[mid] = min_cost
    # Recursively compute left and right halves with narrowed optimal j ranges
    compute_dp(l, mid-1, opt_l, best_j)
    compute_dp(mid+1, r, best_j, opt_r)

# Initialize dp array
dp = [float('inf')] * (N+1)
dp[1] = 0
compute_dp(2, N, 1, N)
print(dp[N])

2. General Approach with CDQ Divide-and-Conquer #

If you can't guarantee the quadrilateral inequality, CDQ divide-and-conquer is a viable general solution that also achieves O(n log n) time. The idea is to split the problem into smaller subproblems, solve the left half first, then compute how the left half contributes to the right half, before solving the right half.

Step-by-Step Breakdown #

1. Split: Divide the indices [1, N] into left [l, mid] and right [mid+1, r] halves.
2. Solve Left: Recursively compute dp[j] for all j in the left half.
3. Compute Contribution: For each i in the right half, find the minimum dp[j] + COST[i][j] where j is in the left half and A[j] ≤ A[i]:
   • Sort the left half by A[j], and the right half by A[i].
   • Use a two-pointer technique to iterate through the sorted right half, inserting valid js (those with A[j] ≤ A[i]) into a segment tree or Fenwick Tree adapted for minimum queries.
   • If COST[i][j] can be decomposed into f(i) + g(j), store g(j) + dp[j] in the tree and query the minimum, then add f(i) to get the candidate value for dp[i].
4. Solve Right: Recursively compute dp[i] for all i in the right half, now including contributions from the left.

Example Code Snippet #

class FenwickTreeMin:
    def __init__(self, size):
        self.n = size
        self.tree = [float('inf')] * (self.n + 1)
    
    def update(self, idx, value):
        while idx <= self.n:
            if value < self.tree[idx]:
                self.tree[idx] = value
            else:
                break  # No need to update further if current value isn't smaller
            idx += idx & -idx
    
    def query(self, idx):
        res = float('inf')
        while idx > 0:
            res = min(res, self.tree[idx])
            idx -= idx & -idx
        return res

def cdq(l, r):
    if l == r:
        return
    mid = (l + r) // 2
    cdq(l, mid)
    
    # Prepare sorted lists of left and right elements
    left = sorted([(A[j], j, dp[j]) for j in range(l, mid+1)])
    right = sorted([(A[i], i) for i in range(mid+1, r+1)])
    
    ptr = 0
    ft = FenwickTreeMin(mid)
    for a_i, i in right:
        # Insert all valid j's from left into the Fenwick Tree
        while ptr < len(left) and left[ptr][0] <= a_i:
            _, j, dp_j = left[ptr]
            ft.update(j, dp_j)
            ptr += 1
        # Query minimum dp[j] and calculate candidate cost
        min_dp_j = ft.query(mid)
        if min_dp_j != float('inf'):
            dp[i] = min(dp[i], min_dp_j + COST[i][j])  # Adjust COST access as needed
    
    cdq(mid+1, r)

# Initialize dp array
dp = [float('inf')] * (N+1)
dp[1] = 0
cdq(1, N)
print(dp[N])

3. Graph-Based Optimization (Dijkstra's Algorithm) #

You can model this problem as a shortest path problem where:

• Nodes are the positions 1 to N.
• There's an edge from j to i (for j ≤ i and A[j] ≤ A[i]) with weight COST[i][j].
• We need the shortest path from node 1 to node N.

The naive approach is O(n²), but we can optimize by only adding necessary edges. For example, maintain a segment tree that tracks the minimal dp[j] for each possible A[j] value. For each i, query the minimum dp[j] + COST[i][j] for all A[j] ≤ A[i] efficiently.

In your example, this method would correctly identify the optimal subsequence 1 → 2 → 5 with total cost 3 + 0 = 3.

内容的提问来源于stack exchange，提问作者Dogey Dog