notes-17-25

         1
       /  
      2    
     /     
    4     

template <class KEY>
struct Node {
  KEY key,
  Node *left = nullptr;
  Node *right = nullptr;
  Node(const KEY &k)  : key{k} {}
}; 

void preorder(Node *p) {
  if (!p) return;
  visit(p->key);
  preorder(p->left);
  preorder(p->right);
}

void levelorder(Node *p) {
  if (!p) return;
  queue<Node *>q;
  q.push(p);
  
  while (!q.empty()) {
    Node *n = q.front();
    q.pop();
    cout << n->key << " ";
    if (n->left) q.push(n->left);
    if (n->right) q.push(n->right);
  }
}

Node *tree_search(Node *x, KEY k) {
  while (x != nullptr && k!= x->key) {
    if (k < x-> key) x = x-> left;
    else x = x-> right;
  }
  return x;
}

void BST_insert(Node *&x, KEY k) {
  if (x == nullptr)
    x = new Node(k);
  else if (k < x-> key)
    BST_insert(x->left, k);
  else 
    BST_insert(x->right, k);
}

Node *tree_min(Node *x) {
  if (x == nullptr)
    return nullptr;
 	while (x->left)
    x = x->left;
  return x;
}

template <class T>
void BinaryTree<T>::remove(Node *&tree, const T &val) {
	Node *nodeToDelete = tree;
  Node *inorderSuccessor;
  
  // first find the position containing the value to remove
  if (!tree) return;
  else if (val < tree->value) remove(tree->left, val);
  else if (val > tree->value) remove(tree->right, val);
  
  // do remove
  else {
    // two trivial cases
    if (tree->left == nullptr) {
      tree = tree->right;
      delete nodeToDelete;
    }
    if (tree->right == nullptr) {
      tree = tree->left;
  		delete nodeToDelete;
    }
    // real shit
    else {
      inorderSuccessor = tree->right;
      //find the inorderSuccessor
      while (inorderSuccessor->left != nullptr){
        inorderSuccessor = inorderSuccessor->left;
      }
      // replace the value of the node with the value of the succssor
      nodeToDelete->value = inorderSuccessor->value;
      // do one more round, just to remove the original inorderSuccessor
      remove(tree->right, inorderSuccessor->value);
    }
  }
}

balance(n) = height(n->left) - height(n->right)

AVL::Node* AVL::rotate_left(AVL::Node* node) {
    Node *rightchild = node->right;
    Node *rightleftchild = rightchild->left;
    node->right->left = node;
    node->right = rightleftchild;
    fixHeightBelow(rightchild);
    return rightchild;
}

AVL::Node* AVL::rotate_right(AVL::Node* node) {
    Node *leftchild = node->left;
    Node *leftrightchild = leftchild->right;
    node->left->right = node;
    node->left = leftrightchild;
    fixHeightBelow(leftchild);
    return leftchild;
}

AVL::Node* AVL::insert_node(AVL::Node* node, int datum) {
    if (node == nullptr) {
        // at a leaf position in the tree, so create a new node
        return new Node{ datum, 1, nullptr, nullptr }; // it has height 1
    }
  
    if (datum < node->datum) {
        node->left = insert_node(node->left, datum);
        node->fix_height(); // remember to fix the height of a node after modifying its children

       // Left Left Case
        if (node->balance()>1 && node->left->balance() >=0) return rotate_right(node);
        // Right Right Case
        if (node->balance()<-1 && node->right->balance()<=0) return rotate_left(node);
        // Left Right Case
        if (node->balance()>1 && node->left->balance()<0) {node->left = rotate_left(node->left);
            return rotate_right(node);}
        // Right Left Case
        if (node->balance()<-1 && node->right->balance()>0) {node->right = rotate_right(node->right); return rotate_left(node);}
    }
    else {
        node->right = insert_node(node->right, datum);
        node->fix_height(); // remember to fix the height of a node after modifying its children

        // Left Left Case
        if (node->balance()>1 && node->left->balance() >=0) return rotate_right(node);
        // Right Right Case
        if (node->balance()<-1 && node->right->balance()<=0) return rotate_left(node);
        // Left Right Case
        if (node->balance()>1 && node->left->balance()<0) {node->left = rotate_left(node->left);
            return rotate_right(node);}
        // Right Left Case
        if (node->balance()<-1 && node->right->balance()>0) {node->right = rotate_right(node->right); return rotate_left(node);}
    }
    return node;
}

#include <limits>
double infty = std::numeric_limits<double>::infinity();

DFS(G):
	mark the root as visited
	push root to stack
	while (stack not empty):
		get and pop top
    for each child of top:
    	if child visited:
    		mark visited
    		push child to top of stack
    		if child is the goal
    			return success
  return failure

class GraphMatrix {
public:
    std::vector<std::vector<int>> matrix; // 邻接矩阵
    int vertices;                         // 顶点数

    // DFS 只能确保在最短路唯一的情况下找到最短路，其他情况找到的路径不是最短的
    int dfs(int start, int target) {
     	  int path_length = 0;
      	std::vector<int> path;
        std::vector<bool> visited(vertices, false);
        std::stack<int> search;
        std::vector<int> parent(vertices, -1);
        search.push(start);
        visited[start] = true;

        while (!search.empty()) {
            int current = search.top(); search.pop();
						
            // found: backtrace
            if (current == target) {
                int v = target;
                path_length = 0;
                while (v != -1) {
                    path.push_back(v);
                    int p = parent[v];
                    if (p != -1) {
                        path_length += matrix[p][v];
                    }
                    v = p;
                }
                return path_length;
            }

            for (int i = 0; i < vertices; ++i) {
                if (matrix[current][i] != 0 && !visited[i]) {
                    visited[i] = true;
                    parent[i] = current;
                    search.push(i);
                }
            }
        }
        return -1;
    }
};

		// BFS 找最短路（仅适用于无权图或等权图）
    int bfs(int start, int end) {
        std::queue<int> q;
        std::vector<bool> visited(vertices, false);
        std::vector<int> distance(vertices, -1);
        std::vector<int> parent(vertices, -1);
        q.push(start);
        visited[start] = true;
        distance[start] = 0;

        while (!q.empty()) {
            int current = q.front();
            q.pop();

            if (current == end) {
                int pathLength = 0;
                int node = end;
                while (node != -1 && node != start) {
                    node = parent[node];
                    pathLength+=1;
                }
                return pathLength;
            }

            for (int i = 0; i < vertices; ++i) {
                if (matrix[current][i] != 0 && !visited[i]) {
                    q.push(i);
                    visited[i] = true;
                    parent[i] = current;
                    distance[i] = distance[current] + 1;
                }
            }
        }
        return -1; // 未找到路径
    }

Dijkstra(G, s)
  for all u ∈ V \ {s}, d(u) = ∞
  d(s) = 0
  R = {}
  while R 6= V
  	pick u not in R with smallest d(u)
  	R = R ∪ {u}
  	for all vertices v adjacent to u
  		if d(v) > d(u) + l(u, v)
  			d(v) = d(u) + l(u, v)

const int INF = INT_MAX;
// 不使用优先队列的 Dijkstra 算法
void dijkstraWithoutPQ(int n, int source, vector<vector<pair<int, int>>> &graph) {
    vector<int> dist(n, INF);       // 最短距离数组
    vector<bool> visited(n, false); // 是否访问过
  
    dist[source] = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        int minDist = INF;
        // 找到未访问节点中距离最小的节点
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[j] < minDist) {
                u = j;
                minDist = dist[j];
            }
        }
        if (u == -1) break; // 所有节点都访问过或者无法到达
        visited[u] = true;

        // 更新相邻节点的距离
        for (auto &edge : graph[u]) {
            int v = edge.first, weight = edge.second;
            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << "Distance from source to node " << i << ": ";
        if (dist[i] == INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
}

// 使用优先队列的 Dijkstra 算法
void dijkstraWithPQ(int n, int source, vector<vector<pair<int, int>>> &graph) {
    vector<int> dist(n, INF); // 最短距离数组
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[source] = 0;
    pq.push({0, source}); // {距离, 节点}

    while (!pq.empty()) {
        auto [curDist, u] = pq.top(); pq.pop();
        if (curDist > dist[u]) continue; // 当前路径不优，不处理
        // 更新相邻节点的距离
        for (auto &edge : graph[u]) {
            int v = edge.first, weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << "Distance from source to node " << i << ": ";
        if (dist[i] == INF) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
}

// 使用优先队列的 Dijkstra 算法，带回溯功能
void dijkstraWithPath(int n, int source, vector<vector<pair<int, int>>> &graph) {
    vector<int> dist(n, INF);          // 最短距离数组
    vector<int> prev(n, -1);           // 前驱节点数组，用于回溯路径
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[source] = 0;
    pq.push({0, source}); // {距离, 节点}

    while (!pq.empty()) {
        auto [curDist, u] = pq.top(); pq.pop();

        if (curDist > dist[u]) continue; // 当前路径不优，不处理

        // 更新相邻节点的距离
        for (auto &edge : graph[u]) {
            int v = edge.first, weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                prev[v] = u; // 记录前驱节点
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果：最短距离和路径
    for (int i = 0; i < n; ++i) {
        cout << "Distance from source to node " << i << ": ";
        if (dist[i] == INF) {
            cout << "INF" << endl;
            continue;
        }
        cout << dist[i] << endl;

        // 回溯路径
        cout << "Path: ";
        vector<int> path;
        for (int at = i; at != -1; at = prev[at]) {
            path.push_back(at);
        }
        reverse(path.begin(), path.end()); // 路径需要反转
        for (size_t j = 0; j < path.size(); ++j) {
            cout << path[j];
            if (j < path.size() - 1) cout << " -> ";
        }
        cout << endl;
    }
}

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);
    graph[0].push_back({1, 10});
    graph[0].push_back({4, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({4, 2});
    graph[2].push_back({3, 4});
    graph[3].push_back({0, 7});
    graph[3].push_back({2, 6});
    graph[4].push_back({1, 3});
    graph[4].push_back({2, 9});
    graph[4].push_back({3, 2});
    
  	std::cout << "Dijkstra without priority queue:" << std::endl;
    dijkstraWithoutPQ(n, 0, graph);
    std::cout << std::endl;
    std::cout << "Dijkstra with priority queue:" << std::endl;
    dijkstraWithPQ(n, 0, graph);
    std::cout << std::endl;
    std::cout << "Dijkstra with priority queue and path:" << std::endl;
    dijkstraWithPath(n, 0, graph);
}

void primMST(vector<vector<pair<int, int>>> &graph, int V) {
    vector<int> key(V, INT_MAX);   // To store the minimum weight for each vertex
    vector<bool> inMST(V, false);   // To check if a vertex is included in the MST
    vector<int> parent(V, -1);      // To store the parent of each vertex in the MST

    key[0] = 0;   // Start from vertex 0
    for (int count = 0; count < V - 1; count++) {
        int minKey = INT_MAX, u;

        // Find the minimum key vertex not included in the MST
        for (int v = 0; v < V; v++) {
            if (!inMST[v] && key[v] < minKey) {
                minKey = key[v];
                u = v;
            }
        }

        inMST[u] = true; // Include the vertex in the MST

        // Update key value and parent for adjacent vertices
        for (auto &edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
            }
        }
    }

    // Print the MST
    cout << "Prim's MST:\n";
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << "\n";
    }
}

void primMSTHeap(vector<vector<pair<int, int>>> &graph, int V) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> key(V, INT_MAX); 
    vector<bool> inMST(V, false); 
    vector<int> parent(V, -1);
    key[0] = 0;
  
    pq.push({0, 0});  // (weight, vertex)
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue;	// ignore if already intie
        inMST[u] = true; // Include the vertex in the MST

        // Update key value and parent for adjacent vertices
        for (auto &edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight;
                parent[v] = u;
                pq.push({key[v], v});
            }
        }
    }

    // Print the MST
    cout << "Prim's MST using Heap:\n";
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << "\n";
    }
}

// Union-Find Disjoint Set data structure
struct DisjointSet {
    vector<int> parent, rank;
    DisjointSet(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};


void kruskalMST(vector<Edge> &edges, int V) {
    sort(edges.begin(), edges.end(), compareEdges);

    DisjointSet ds(V);
    vector<Edge> mst;

    for (auto &edge : edges) {
        if (ds.find(edge.src) != ds.find(edge.dest)) {
            mst.push_back(edge);
            ds.unite(edge.src, edge.dest);
        }
    }

    // Print the MST
    cout << "Kruskal's MST:\n";
    for (auto &edge : mst) {
        cout << edge.src << " - " << edge.dest << "\n";
    }
}

// complexity: O(V + E)
bool is_graph_cyclic(const vector<vector<int>> &adj_list) {
    unordered_set<int> visited;

    // Since the graph is connected, we only need to start from one node (e.g., node 0 or 1)
    return hasCycleDFS(0, -1, adj_list, visited);
}

bool hasCycleDFS(int node, int parent, 
                const vector<vector<int>>& adjList, 
                unordered_set<int>& visited) {
    visited.insert(node);

    for (int neighbor : adjList[size_t(node)]) {
        // If the neighbor is not visited, recurse
        if (visited.find(neighbor) == visited.end()) {
            return hasCycleDFS(neighbor, node, adjList, visited);
        }
        // If the neighbor is visited and not the parent, we found a cycle
        else {
          if (neighbor != parent)
            return true;
        }
    }
    // reach here: all neighbors are visited, and not parent, then ends
    return false;
}


int main() {
    // Example: Input graph
    const vector<vector<int>> adjList = {
        {2, 3}, //0
        {2},  //1
        {0, 1}, //2
        {0} //3
    };

    if (is_graph_cyclic(adjList)) {
        cout << "Graph contains a cycle" << endl;
    } else {
        cout << "Graph does not contain a cycle" << endl;
    }

Algorithm checknode(node v)
	if (promising(v))
		if (isSol(v))
			done
		else
			for each node u adjacent to v
				checknode(u)

Algorithm checknode(node v)
	if (isSol(v))
		good, add to solution set
	else
		for each node u adjacent to v
			if (promising(u))
				checknode(u)

void NQueens::solve() {
    putQueen(0);
}

// promising if would not violate any constraints
bool NQueens::promising(uint32_t row, uint32_t col) {
    return   column[col] == AVAILABLE
        && leftDiagonal[row + col] == AVAILABLE
        && rightDiagonal[row - col + (size - 1)] == AVAILABLE;
}  // NQueens::promising()

// Place a queen in row
// If display == true, display each board as a solution is found
void NQueens::putQueen(uint32_t row) {
    // 如果这个时候已经 proceed 到了最后行, 说明这是一个 sol.
    if (row == size) {++solutions;return;} 

    // Check every column within this row
    for (size_t col = 0; col < size; ++col) {
        // Check if proposed placement is promising
        if (promising(row, col)) {
            // Make the move, and a recursive call to next move
            positionInRow[row] = col;
            column[col] = !AVAILABLE;
            leftDiagonal[row + col] = !AVAILABLE;
            rightDiagonal[row - col + (size - 1)] = !AVAILABLE;
            putQueen(row + 1);

            // Undo this move and thus backtrack
            column[col] = AVAILABLE;
            leftDiagonal[row + col] = AVAILABLE;
            rightDiagonal[row - col + (size - 1)] = AVAILABLE;
        }  // if
        ++tried;
    }  // for
}  // NQueens::putQueen()

const int INF = numeric_limits<int>::max();
struct Node {
    int level;       // 当前深度
    int cost;        // 当前路径的代价
    int bound;       // 当前节点的下界
    vector<int> path; // 当前路径
    // PQ 比较函数，小的优先
    bool operator<(const Node& other) const {
        return bound > other.bound;
    }
};

// 计算给定矩阵的最小边界
int calculateBound(const vector<vector<int>>& dist, const vector<int>& path, int n) {
    int bound = 0;
  
    // 标记已经访问的城市
    vector<bool> visited(n, false);
    for (int city : path) visited[city] = true;

    // 加上路径中已有的代价
    for (size_t i = 1; i < path.size(); ++i) {
        bound += dist[path[i - 1]][path[i]];
    }

    // 为未访问的城市估计下界
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            int minCost = INF;
            for (int j = 0; j < n; ++j) {
                if (i != j && !visited[j]) {
                    minCost = min(minCost, dist[i][j]);
                }
            }
            if (minCost != INF) bound += minCost;
        }
    }

    return bound;
}

// TSP 分支限界主函数
int tspBranchAndBound(const vector<vector<int>>& dist) {
    int n = dist.size();
    priority_queue<Node> pq; // 优先队列，按节点的下界排序
    int bestCost = INF;      // 当前最优解
    vector<int> bestPath;    // 最优路径

    // 初始节点
    Node root;
    root.level = 0;
    root.cost = 0;
    root.path = {0}; // 从城市 0 开始
    root.bound = calculateBound(dist, root.path, n);
    pq.push(root);

    // 分支限界搜索
    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        // 如果当前节点的下界大于最优解，剪枝
        if (curr.bound >= bestCost) continue;

        // 如果当前路径包含所有城市并回到起点
        if (curr.level == n - 1) {
            // 计算完整路径的代价
            int totalCost = curr.cost + dist[curr.path.back()][0];
            if (totalCost < bestCost) {
                bestCost = totalCost;
                bestPath = curr.path;
                bestPath.push_back(0); // 回到起点
            }
            continue;
        }

        // 生成子节点
        for (int i = 0; i < n; ++i) {
            if (find(curr.path.begin(), curr.path.end(), i) == curr.path.end()) {
                Node child;
                child.level = curr.level + 1;
                child.path = curr.path;
                child.path.push_back(i);
                child.cost = curr.cost + dist[curr.path.back()][i];
                child.bound = child.cost + calculateBound(dist, child.path, n);

                // 如果下界小于当前最优解，加入优先队列
                if (child.bound < bestCost) {
                    pq.push(child);
                }
            }
        }
    }

    // 输出最优路径
    cout << "最优路径: ";
    for (int city : bestPath) {
        cout << city << " ";
    }
    cout << endl;

    return bestCost;
}


int main() {
    // 示例：距离矩阵
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    int result2 = tspBranchAndBound(dist);
    cout << "Shortest path by branch and bound: " << result2 << endl;

    return 0;
}

uint64_t naiveFibo(uint32_t i) {
    if (i == 1 || i == 0) return i;
    return naiveFibo(i-1) + naiveFibo(i-2);
}

uint64_t topDownFibo(uint32_t n) {
    static uint64_t memo[MAX_FIB + 1] = {0, 1}; //initial value
    // if n is too large, not in range of service
    if (n > MAX_FIB) return 0;
    // if already computed, return the value
    if (memo[n] > 0 || n==0) return memo[n];

    memo[n] = topDownFibo(n-1) + topDownFibo(n-2);
    return memo[n];
}

uint64_t bottomUpFibo(uint32_t n) {
    static uint64_t memo[MAX_FIB + 1] = {0, 1}; //initial value
    for (uint32_t i = 2; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}

uint64_t binomialCoeffRecursion(uint32_t n, uint32_t k) {
    if (k == 0 || k == n) return 1;
    return binomialCoeffRecursion(n-1, k-1) + binomialCoeffRecursion(n-1, k);
}

uint64_t binomialCoeffHelper(uint32_t n, uint32_t k, vector<vector<uint64_t>>& memo) {
    if (k == 0 || k == n) {
        memo[k][n] = 1;
        return 1;
    }
    if (memo[k][n] > 0) return memo[k][n];
    memo[k][n] = binomialCoeffHelper(n-1, k-1, memo) + binomialCoeffHelper(n-1, k, memo);
    return memo[k][n];
}

uint64_t binomialCoeffTopDown(uint32_t n, uint32_t k) {
    vector<vector<uint64_t>> memo(k+1, vector<uint64_t>(n+1, 0));
    return binomialCoeffHelper(n, k, memo);
}

uint64_t binomialCoeffBottomUp(uint32_t n, uint32_t k) {
    vector<vector<uint64_t>> memo(k+1, vector<uint64_t>(n+1));
    for (size_t i = 0; i <= k; i++) {
        for (size_t j = i; j <= n; j++) {
            if (i==j || i==0) memo[i][j] = 1;
            else memo[i][j] = memo[i-1][j-1] + memo[i][j-1];
        }
    }
    return memo[k][n];
}

int knightMoveDP(int plateWidth, int totalMoves, int startX, int startY, int destX, int destY) {
    // Initialize a 3D DP table with all zeros
    vector<vector<vector<int>>> dp(totalMoves + 1, vector<vector<int>>(plateWidth, vector<int>(plateWidth, 0)));
    
    // Base case: starting position
    dp[0][startX][startY] = 1;

    // Fill DP table
    for (int k = 1; k <= totalMoves; ++k) {
        for (int x = 0; x < plateWidth; ++x) {
            for (int y = 0; y < plateWidth; ++y) {
                if (dp[k - 1][x][y] > 0) { // If there are paths to this cell
                    for (auto move : knightMoves) {
                        int nx = x + move.first;
                        int ny = y + move.second;
                        if (nx >= 0 && nx < plateWidth && ny >= 0 && ny < plateWidth) { // Valid move
                            dp[k][nx][ny] += dp[k - 1][x][y];
                        }
                    }
                }
            }
        }
    }

    // Print the entire chessboard for the K-th step
    cout << "Chessboard at step " << totalMoves << ":" << endl;
    for (int x = 0; x < plateWidth; ++x) {
        for (int y = 0; y < plateWidth; ++y) {
            cout << dp[totalMoves][x][y] << " ";
        }
        cout << endl;
    }

    // Return the number of paths to (tx, ty) after K moves
    return dp[totalMoves][destX][destY];
}


/*
Chessboard at step 4:
16 0 17 0 18 0 7 0 
0 10 0 22 0 8 0 7 
17 0 16 0 23 0 10 0 
0 22 0 36 0 14 0 9 
18 0 23 0 18 0 9 0 
0 8 0 14 0 6 0 4 
7 0 10 0 9 0 6 0 
0 7 0 9 0 4 0 0    
*/  

// TSP 动态规划解法
int tsp(int n, const vector<vector<int>>& cost) {
    // dp[mask][i] 表示从起点 0 出发，经过 mask 表示的所有城市，最后停留在城市 i 的最短路径长度
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    // 初始状态，从起点 0 出发，路径长度为 0
    dp[1][0] = 0;

    // 遍历所有状态 mask
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            // 如果城市 i 不在当前 mask 中，跳过
            if (!(mask & (1 << i))) continue;

            // 尝试从集合 mask 中的其他城市转移到 i
            for (int j = 0; j < n; ++j) {
                if (j != i && (mask & (1 << j)) && dp[mask ^ (1 << i)][j] != INT_MAX) {
                    dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + cost[j][i]);
                }
            }
        }
    }

    // 最后计算从每个终点返回起点的最短路径
    int result = INT_MAX;
    for (int i = 1; i < n; ++i) {
        if (dp[(1 << n) - 1][i] != INT_MAX) {
            result = min(result, dp[(1 << n) - 1][i] + cost[i][0]);
        }
    }

    return result;
}

// Divide and Conquer(top down)
quicksort(array)
	partition;
	quicksort(left)
	quicksort(right)

// Combine and Conquer(bottom up)
mergesort(array)
	merge_sort(left);
	merge_sort(right);
	merge(left, right);

// 0-1 Knapsack Function
int knapsack(const vector<int>& weights, const vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    // Input: weights, values, and max capacity of knapsack
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int W = 8;

    int max_value = knapsack(weights, values, W);
    cout << "Maximum value that can be obtained: " << max_value << endl;

    return 0;
}
//Maximum value that can be obtained: 10

const int INF = INT_MAX;

void floydWarshall(vector<vector<int>>& graph) {
    int V = graph.size();
    vector<vector<int>> dist = graph;

    // 三重循环
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                // 如果通过 k 能连接 i 和 j，并且减少路径距离
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出结果
    cout << "Shortest distances between every pair of vertices:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main() {
    // 输入：邻接矩阵表示的图 (无穷大用 INF 表示)
    vector<vector<int>> graph = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };

    floydWarshall(graph);

    return 0;
}

/*
Shortest distances between every pair of vertices:
0 3 5 6 
5 0 2 3 
3 6 0 1 
2 5 7 0  
*/

// How much you pay for a discounted (25% off) meal.
cost discounted(cost full_price) {
    return full_price * 3 / 4;
}

cost best_price(const std::vector<cost>& prices) {
    // NOTE: if you use a bottom-up approach, initialize your table with
    // std::numeric_limits<cost>::max()/4 ... you MUST divide by 4!
    if (prices.size() == 0) {
        return 0;
    }

    std::vector<std::vector<cost>> dp(6, std::vector<cost>(prices.size(), std::numeric_limits<cost>::max()/4));
    
    // base case: 第一次没有 punch card
    dp[0][0] = discounted(prices[0]);
    dp[1][0] = prices[0];

    for (size_t j = 1; j < prices.size(); ++j) {
        for (size_t i = 0; i < 6; ++i) {
            if (i == 0) {
                // Min(第 j-1 个 order 结束攒了 0 个 fullpay 点数的钱 + 第 j 个 order 使用 discount 的钱,
                //     第 j-1 个 order 结束攒了 5 个 fullpay 点数的钱 + 第 j 个 order 消耗 5 fullpay 免费)
                dp[i][j] = std::min(discounted(prices[j]) + dp[0][j-1], dp[5][j-1]);
            } else {
                // Min(第 j-1 个 order 结束攒了 i-1 个 fullpay 点数时的钱 + 第 j 个 order pay full 的钱攒点数, 
                //     第 j-1 个 order 结束攒了 i 个 fullpay 点数时的钱   + 第 j 个 order 使用 discount 的钱)
                dp[i][j] = std::min(prices[j] + dp[i-1][j-1], discounted(prices[j]) + dp[i][j-1]);
            }
        }
    }
    return dp[0][prices.size() - 1];
}