First, let's clarify what your problem actually translates to: you're trying to find the maximum independent set in a graph where:

• Each node represents an element in array A
• An edge exists between two nodes if match_check(Wi, Wj) returns True (i.e., the two elements share at least 3 rounded decimal positions)

Maximum independent set is an NP-hard problem for general graphs—meaning there's no known polynomial-time algorithm to solve it exactly unless P=NP. That context is key to understanding why your current DP approach isn't delivering the optimization you hoped for.

Why Your Current DP Has O(2^n) Time Complexity #

Let's break down the issue with your implementation:

• You're using start|end as the key for lookup_dict, but your recursive function's behavior also depends entirely on curr_items—the list of elements you've selected so far.
• The problem here is that curr_items adds an exponential number of unique states. For each start value, there are 2^start possible subsets of elements you could have selected up to that point. Your lookup_dict doesn't account for these different subsets, so the cache rarely hits, and you end up enumerating every possible combination of selecting or rejecting elements—just like a brute-force recursive approach.

In short, your DP isn't actually reducing the problem's complexity because the state doesn't capture the necessary information without including the entire selected subset, which is exponentially large.

What a "Useful" DP Would Look Like (and Its Limits) #

If you wanted to structure a DP approach that explicitly uses memoization for this problem, you'd likely need to use a bitmask to represent the selected elements (only feasible for small n). For example:

• State: dp[mask] = size of the largest valid subset for the elements included in mask (each bit in mask represents whether an element is selected)
• Transition: For each element, if adding it to the subset doesn't conflict with any already selected elements, update dp[mask | (1<<i)] = max(dp[mask | (1<<i)], dp[mask] + 1)

But even this approach has a time complexity of O(n*2^n), which is still exponential—it's just a more efficient brute-force, not a polynomial optimization. For n larger than ~20, this becomes infeasible.

Practical Alternatives #

Since exact solutions are impractical for large n, you might want to consider:

• Heuristic algorithms: Greedy approaches (e.g., repeatedly removing the node with the highest degree, then adding its non-neighbors to the set) that give a good approximate solution.
• Special case checks: If your graph has a specific structure (e.g., it's bipartite), you can use Konig's theorem to convert the problem to a maximum matching problem, which can be solved in polynomial time. But this only applies if your match_check relation forms a bipartite graph (unlikely unless there's a hidden structure in your data).

内容的提问来源于stack exchange，提问作者Yash Mishra