tags:
  - Notes

Real-Basic Algorithm Concepts

Recursion

递归是一种通过将重复的问题分解为子问题来解决的算法。比方说求从 1 加到 n 的值，我们就可以用递归来解决。递归的特征就是自身调用和存在终止条件。下面是一个简单的例子：

int sum(int n){
	if(n <= 0){
		return -1;
	}
	if(n = 1){
		return 1;
	}
	return sum(n - 1) + n;
}

由于每次的函数调用都会创建出一个栈帧用于存储局部变量和临时变量，所以递归程序应尽量简洁，并避免递归调用层次，避免栈溢出。

Back-Tracking

使用穷举解决问题的方法

def solveNQueens(N):
    def isValid(board, row, col):
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def solve(board, row):
        if row == N:
            result.append(board[:])
            return
        for col in range(N):
            if isValid(board, row, col):
                board[row] = col
                solve(board, row + 1)
                board[row] = -1  # 回溯

    result = []
    solve([-1] * N, 0)
    return result

Greedy Algorithm

Divide-and-Conquer

处理问题的思路

归并