今天來寫點雜記和更多的 Leetcode :)

11.7 把樹對應到 Hamming Distance

距離標籤是個有趣的概念，如果想要讓計算距離的過程更加簡化，可以考慮將距離標籤想像成賦距空間(metric space)內的某個點。今天來想想看一個簡單的腦力激盪：把一棵樹的節點建立一個二元字串，使得兩個節點之間的距離恰好是這兩個點標籤中，不同的字元數量。

我們可以將每個點給一個長度為 n-1 的二元字串：每一個字元對應到樹上的一條邊，這條邊可以把樹切成兩半，我們可以把其中一半的點對應到 0 這個字元、另一半的點對應到 1 這個字元。那麼，對於樹上任兩點，其對應到的字串之間的相異字元位置，恰好就對應到這兩點之間的路徑上的那些邊。

11.8 更多的 Leetcode

Leetcode 1928. Minimum Cost to Reach Destination in Time

https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/
題目大意：地圖上有N座城鎮，你想要從編號 0 走到編號 N-1 的城鎮。每經過一個城鎮(包含起訖點)都需要收 passingFees[i] 的費用。每條雙向道路都有一個旅行需要的時間。求旅行時間不超過 maxTime 的所有路線中，總花費最少的費用。(maxTime <= 1000; N <= 1000)
解題思考：這題可以用動態規劃。我們利用 dp(t, x) 表示到達位置 x 使用總時間 t 需要的最少花費。注意到所有旅行時間都是正整數，因此可以從小的 t 到大的 t 逐步進行動態規劃。

class Solution {
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n = passingFees.size();
        int m = edges.size();
        int dp[1005][1005];
        memset(dp, -1, sizeof(dp));
        vector<vector<int>> adj(n);
        for (int i = 0; i < m; i++) {
            adj[edges[i][0]].push_back(i);
            adj[edges[i][1]].push_back(i);
        }
        
        dp[0][0] = passingFees[0];
        for (int t = 0; t <= maxTime; t++) {
            for (int x = 0; x < n; x++) {
                if (t > 0 && dp[t-1][x] != -1 && (dp[t][x] == -1 || dp[t][x] > dp[t-1][x])) dp[t][x] = dp[t-1][x];
                if (dp[t][x] != -1 && (t == 0 || dp[t][x] != dp[t-1][x])) {
                    for (int i : adj[x]) {
                        int y = edges[i][0] + edges[i][1] - x;
                        int z = t + edges[i][2];
                        int c = dp[t][x] + passingFees[y];
                        if (z <= maxTime && (dp[z][y] == -1 || dp[z][y] > c)) {
                            dp[z][y] = c;
                        }
                    }
                }
            }
        }
        
        int minCost = -1;
        for (int t = 0; t <= maxTime; t++) {
            if (dp[t][n-1] != -1 && (minCost == -1 || minCost > dp[t][n-1]))
                minCost = dp[t][n-1];
        }
        return minCost;
        
    }
};