2Brute2Best
🔥0
03

Prefix segmentation (DP — 1D Linear Sub-pattern)

dp[i] asks about the whole prefix of length i, and the rule tries every last piece s[j..i), reading dp[j] for many j.

Signals in the problem statement
  • ›

    "can the string be segmented into dictionary words"

  • ›

    "fewest pieces / squares that add up to n"

  • ›

    the last piece can have many lengths

What makes it different

Each cell reads many earlier cells (not just two), so the table stays O(N) and time is O(N · piece choices). Greedy "take the longest piece" fails — always try them all.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Word Break
    Basic Anchor·LeetCode #139
    Medium
  2. 2
    Perfect Squares
    Pattern Transfer·LeetCode #279
    Medium

Template

word-break-template.cpp
// Prefix segmentation: dp[i] = the first i characters can be split into words.
// Try every last piece s[j..i) and read dp[j].
bool canSplit(const string& s, const vector<string>& words) {
    unordered_set<string> dict(words.begin(), words.end());
    size_t longest = 0;
    for (auto& w : words) longest = max(longest, w.size());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;                                  // the empty prefix splits trivially
    for (int i = 1; i <= n; i++)
        for (int j = i - 1; j >= 0 && i - j <= (int)longest; j--)
            if (dp[j] && dict.count(s.substr(j, i - j))) { dp[i] = true; break; }
    return dp[n];
}
Remember this · DP — 1D Linear
Trigger
"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.
Think
If I knew the answer for every smaller prefix, how would I get the answer for i?
Key question
What does dp[i] mean in one sentence?
Take or skip