題目連結

經典 LIS 加 path printing 題。

題目連結

掰咖的n皇后問題，如果我們拿 column 來看的話，他只跟前一個 column 有關而已了！

令 $dp[i][j]$ 為 把皇后擺在 row $i$ column $j$ 這個位置的話，有幾種擺法。

因此

1. 如果這個 column 沒有指定后位的話，我們就 $dp[i][j] += dp[k][j - 1]$ where $1 \leq k < n, |{i-k}| > 1$
2. 如果這個 column 有指定后位的話，我們就 $dp[queenPosition][j] += dp[k][j - 1]$ where $1 \leq k < n, |{i-k}| > 1$

題目連結

非常好的題目！先想三維再想二維！

核心的想法是，如果能延伸，我們就延伸！延伸長度的話呢？枚舉他！

題目連結

想想看，與其窮舉所有的 substring ，我們改成: 對於每一個 $S[i] $，看看有哪些子字串計算unique時會算到 $S[i]$！

對於每一個 $S[i]$，我們找出他的最遠左右端點，端點內的 $S[j]$ 要符合 $S[i] \neq S[j]$ 且 $0 <= j < S.length()$。因此，我們可以輕鬆得到包含 $S[i]$ 的 substring 會有 $(i - left + 1) * (right - i + 1)$ 個啦！

題目連結

2 pointers 小範圍可以做，只是這題範圍太大…

那轉用數學吧！

假設某一種合法的答案為 $$N = (s+1) + (s+2) + (s+3) + … + (s+k)$$ 那我們可以推得 $$N = s*k + \frac{(1 + k) * k}{2}$$ $$2N = k(2s + k + 1)$$

我們可以觀察到 $2N > k$，進一步觀察右邊其實有 $k^2$，所以其實我們的搜尋範圍只有 $2N > k^2$