# 演算法實作 Using C++

## 目錄
> :::spoiler
> [TOC]
> :::
---

## 插入排序法(少量最快)

## 動態規劃(Dynamic Programming)

## 二元樹

## 求解n層河內塔(含路徑過程)

## spfa特化演算法(競賽求最短優先)

## DFS

> Depth-First Search 用於遍歷和搜尋Tree和Graph。以深度為優先順序進行搜索，從起點開始，儘可能深入地訪問每個鄰接節點，直到到達無法再深入的節點或找到目標節點為止。通常使用遞迴或Stack實現。可用於例如迷宮問題、拓撲排序、連通性等。

### Sample Question
> 每次只能前進1或2格，輸入n為目標格數，輸出從起點1到終點n的方法有幾種

//sample 1: 將主block整合呼叫自己與加總分支計算值
#include <iostream>
using namespace std;

// dfs函數，now為目前所在樓層，tg為目標樓層
int dfs(int now, int tg) {
    // 已達終點
    if (now == tg) {
        //剛好達到終點傳回1
        return 1;
    }
    // 已超過終點
    if (now > tg) {
        return 0;
    }
    
    // 創造+1跟+2兩種方法的分支，並讓返回值加總
    // 因為剛好達到終點會回傳1，此處進行相加即可達到所有分支達到終點後加總的效果
    return dfs(now + 1, tg) + dfs(now + 2, tg);
}

int main() {
    int n;
    cin >> n;
    // 從1開始搜尋到終點n的方法數
    cout << dfs(1, n) << endl;
    
    return 0;
}

//sample 2: 將呼叫自身的方法分離，並用counter另外加總不同方法分支回傳值，最終只回傳counter
#include <iostream>
using namespace std;

// dfs函數，now為目前所在樓層，tg為目標樓層
int dfs(int now, int tg) {
    // 已達目標
    if (now == tg) {
        //剛好達到終點傳回1
        return 1;
    }
    // 已超過目標
    if (now > tg) {
        return 0;
    }

    int counter = 0;
    // 往上一層樓繼續搜尋
    counter += dfs(now + 1, tg);
    // 往上兩層樓繼續搜尋
    counter += dfs(now + 2, tg);
    //counter在以上兩種方法分支產生後，會將剛好達到終點的回傳值1加入counter中
    
    // 返回counter即是所有分支最後加總能達到終點的方法數
    return counter;
}

int main() {
    int n;
    cin >> n;
    // 從1開始搜尋到終點n的方法數
    cout << dfs(1, n) << endl;
    
    return 0;
}

## Dijkstra演算法

## LCS(最長共同子序列)

## LIS(最長(嚴格/非嚴格)遞增子序列)

## Kadane's (最大連續和)

> 輸入一個數列，找出子序列加總中最大值

int sum = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;

    sum += x;
    max_sum = max(max_sum, sum);
    sum = max(sum, 0);
}
cout << sum << endl;

## 著色判斷

## 其他結構筆記

### 遞迴函數
> 在新增遞迴函數時需要將function拆分為兩個block看待，通常用if架構分隔
> 1. 用於計算的block，最後return的是這條分支的計算結果
> 2. 用於返回最終統整結果的主要block，在這裡最後return時呼叫自身，創造分支進入計算block，經過層層return回來後配合operator，才return最終結果回main function

> 求n階層

#include <iostream>
using namespace std;

int fac(int n) {
    if (n == 0 || n == 1) { // 計算block
        return 1;
    }
    else { // 主block
        return n * fac(n - 1);//呼叫自己，創造分支進入計算block
    }
}

int main() {
    int n;
    cin >> n;
    cout << n << " 階層 =  " << fac(n) << endl;
    return 0;
}

### 地圖座標建構
使用Vector配合自定結構

#include <iostream>
#include <vector>

struct Point {
    int x;
    int y;
};

int main() {
    int N;
    cin >> N;
    
    vector<Point> points(N);
    for (int i = 0; i < N; i++) {
        cin >> points[i].x >> points[i].y;
    }
}

---
###### tags: `Data Structure and Algorithms` `C++`