題目連結

For every $dp[i] = k$, we define $i$ as the collection of people that’re not paired yet, and $k$ is the minimum cost to pair those people up, if possible.

Starting with (1 << n) - 1, we can pair 2 of them at a time, and recurse on (state ^ (1 << i) ^ (1 << j)).

Notice the base case is $dp[0] = 0$.

題目連結

位元DP。

我們定義 $dp[i][j] = k$, $j$ 為已經拾取過果實的地方，$i$ 為最後所停之處，$dp[i][j]$為拾取果實後停在$i$的總步數。

初始化的話，$dp[i][1<<i] = $ 從出發點到此的距離，其餘 $\infty$。

計算的話，假設我們有三個點，我們現在要求取$dp[0][3]$（已經在0, 1拿完果實，並停在0），那我們的其中一種可行走法為$dp[1][2] + dist[1][0]$，也就是說，從只去過1的狀態走到0來！所以更新的話，就是:

1
2

dp[i][j] = min(dp[i][j], dp[k][j - (1 << i)] + dist[i][k]);

題目連結

2D prefix sum!

枚舉起始行、結束行、跟列！這樣就可以轉回 1D 的 prefix sum 題目了。

題目連結

經典的最少矩陣乘法次數，但是要輸出最終結果！

第一次使用 tuple，感覺不錯。

1. tuple<type, type, ...>
2. make_tuple(var, var)
3. get<index> tupleName
4. c++ int a; int b; tie(a, b) = someReturnedTuple

題目連結

BFS 變形，走的一步其實是多步（一次走到底）