动态规划 Dynamic Programming

动态规划算法是一种分而治之的算法，其应用之广泛，是刷题必备的理论。其过程如下：
Characterize the structure of an optimal solution
Recursively define the value of an optimal solution.
Compute the value of anoptimal solution,typically in a bottom-up fashion.
Construct an optimal solution from computed information.

1. 斐波那契数列 Fibonacci Sequence

def fibonacci(n):
    assert n > 0
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n) + fibonacci(n+1)

上述代码问题在于，随着N的增大，展开的节点成指数级增长，很多的节点其实被重复计算了。解决的办法很简单，用一个字典记录之前的计算，下次遇到这种节点就不用再算了，直接取字典值就好，即用空间换时间：

fib = {1: 1, 2: 1}
def fibonacci(n):
    assert n > 0
    if n in fib:
        return fib[n]
    else:
        fib[n] = fibonacci(n-1) + fibonacci(n-2)
        return fib[n]

2. 背包问题 Knapsack Problem

\begin{aligned}\text{maximize} \quad &\sum_{i=1}^m p_i' x_i\\\text{subject to} \quad &\sum_{i=1}^mw_i' x_i \leq W, x \in \{0, 1\}\end{aligned}

我们设剩余 $n$ 个物品，剩余可用重量为 $W_n$ , 目前最大价值为 $P_n$

当 $n=m$ 时， $P_n = 0, W_n = W$
当 $n=m-1$ 时，

P_n = \max \begin{cases}& p_{n+1} + P_{n-1}, & x_{n+1} = 1 \\& P_{n-1}, & x_{n+1} = 0\end{cases} \\W_n = \begin{cases}& W - w_{n+1}, \quad & x_{n+1} = 1 \\& W_{n+1}, \quad & x_{n+1} = 0\end{cases}

当 $n=0$ 或 $W_n < w_n$ 时，返回 $P_n$

p = [11,21,31,33,43,43,55,65]
w = [1,11,21,23,33,43,45,55]
W = 110
def knapsack(wn, pn, n):
    if wn < w[n-1] or n == 0:
        return pn
    else:
        p_choose = knap_sack(wn - w[n-1], pn + p[n-1], n-1)
        np_choose = knap_sack(wn, pn, n-1)

        if p_choose >= np_choose:
            return p_choose
        else:
            return np_choose

print(knapsack(W, 0, len(p)))

实验结果为151

为了保留搜索过程，我们用Binary Tree来解

class Node:
    def __init__(self, indices, z, w, parrent=None, left=None, right=None):
        self.parrent = parrent
        self.left = left # Choose Current
        self.right = right # Not Choose
        self.indices = indices 
        self.z = z # Current Value
        self.w = w # Current Weight Left
        
class Solution:
    p = [11,21,31,33,43,43,55,65]
    w = [1,11,21,23,33,43,45,55]
    W = 110

    assert len(p) == len(w)
    N = len(w)

    def build_tree(self, parrent):
        if len(parrent.indices) == 0:
            return
        else:
            index = parrent.indices[0]
            if parrent.w <= self.w[index]:
                return

            # Choose k[0]
            z = parrent.z + self.p[index]
            w = parrent.w - self.w[index]
            left_node = Node(parrent.indices[1:], z, w, parrent)
            
            # Not choose k[0]
            right_node = Node(parrent.indices[1:], parrent.z, parrent.w, parrent)

            parrent.left = left_node
            parrent.right = right_node

            self.build_tree(left_node)
            self.build_tree(right_node)

    def walk_tree(self, node):
        if node.left is None and node.right is None:
            if node.z > self.best.z:
                self.best = node
                return

        else:
            self.walk_tree(node.left)
            self.walk_tree(node.right)

    def print_path(self, node):
        if node.parrent is not None:
            if node.parrent.left == node:
                print("Choose ", node.parrent.indices[0], ", W left:", node.w, ", Current Price", node.z)
            elif node.parrent.right == node:
                print("Not Choose ", node.parrent.indices[0], ", W left:", node.w, ", Current Price", node.z)
            self.print_path(node.parrent)

    def solve(self):
        # Build the tree
        root = Node(list(range(self.N)), 0, self.W)
        self.build_tree(root)

        # Walk to find max
        self.best = root
        self.walk_tree(root)

        # Print result
        self.print_path(self.best)

3. 八皇后问题 Eight Queens Puzzle

八皇后问题是指在国际象棋棋盘上放置8个皇后棋子，使得任意两个棋子之间不能互相攻击。

皇后棋子会攻击位于其同行，同列，以及同一条45度斜线上的所有棋子。

问题如出一辙，解法如下

import numpy as np
import random

class BoardNode:
    def __init__(self, board, last_place=None, queen_left=8, parrent=None, children=None):
        self.board = board
        self.parrent = parrent
        self.children = children
        self.queen_left = queen_left
        self.last_place = last_place

    def is_full(self):
        return self.board.sum() == 64

    def place_at(self, i, j):
        board = np.copy(self.board)
        board[i, :] = 1
        board[:, j] = 1

        for dx in range(-8, 8):
            if 0 <= i + dx < 8 and 0 <= j + dx < 8: 
                board[i+dx, j+dx] = 1
            if 0 <= i - dx < 8 and 0 <= j + dx < 8:
                board[i-dx, j+dx] = 1
        return board

    def places(self):
        if self.last_place is None:
            start_i = 0
        else:
            start_i = self.last_place[0]
        return [(i, j) for i in range(start_i, 8) for j in range(8) if self.board[i, j] != 1]

def print_board(board):
    out = ""
    for row in board:
        for x in row:
            if x == 0:
                out += " + "
            else:
                out += " X "
        out += " \n"
    print(out)
    return out

class EightQuees:
    solution = None
    count = 0
    board = np.zeros((8, 8), dtype=np.int)
    places = []

    def build_tree(self, node):
        if node.is_full():
            if node.queen_left == 0:
                self.solution = node
                self.count += 1
                print(self.count)

                self.places = []
                self.board = np.zeros((8, 8), dtype=np.int)
                self.print_node(self.solution)
                print_board(self.board)
                print(self.places)
            return

        elif node.queen_left > 0:
            for place in node.places():
                board = node.place_at(*place)
                child = BoardNode(board, place, node.queen_left-1, node)
                node.children = child
                self.build_tree(child)        
    
    def print_node(self, node):
        if node.last_place is not None:
            self.board[node.last_place] = 1
            self.places.append(node.last_place)
        if node.parrent is not None:
            self.print_node(node.parrent)

    def solve(self):
        root = BoardNode(np.zeros((8, 8), dtype=np.int))
        self.build_tree(root)

4. 旅行商问题 Traveling Salesman Problem

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

用数学语言表达：

\begin{aligned}\text{minimize}\quad & \sum_{i=0}^n\sum^n_{j\neq i} c_{ij}x_{ij}\\\text{subject to} & \quad x_{ij} \in \{0, 1\}\\ &\sum_{i=0, i\neq j}x_{ij} = 1\\ &\sum_{j=0,j\neq i}x_{ij}=1\end{aligned}

where $c_{ij}$ represents path cost from city $i \rightarrow j$ , $x_{ij}$ represents path exists from city $i\rightarrow j$ and vice versa.

import numpy as np
import random

class Node:
    def __init__(self, unvisited, cost, last_city=None, first_city=None, parrent=None, children=None):
        self.unvisited = unvisited
        self.last_city = last_city
        self.first_city = first_city
        self.cost = cost
        self.parrent = parrent
        self.children = children
    
    def is_leaf(self):
        return len(self.unvisited) == 0
    
class TSP:
    solution = None
    cost = [
        [0, 3, 6, 7],
        [5, 0, 2, 3],
        [6, 4, 0, 2],
        [3, 7, 5, 0]
    ]
    cities = list(range(len(cost)))

    def print_path(self, node):
        cities = []
        print('Best cost:', node.cost)
        while node.parrent is not None:
            cities.append(node.last_city)
            node = node.parrent
        print(list(reversed(cities)))

    def walk_tree(self, node):
        if node.is_leaf():
            if node.cost < self.best.cost:
                self.best = node
                return
        else:
            for child in node.children:
                self.walk_tree(child)

    def build_tree(self, node):
        if node.is_leaf():
            return
        else:
            children = []
            for city in node.unvisited:
                c = 0 if node.last_city is None else self.cost[node.last_city][city] + node.cost
                first_city = city if node.first_city is None else node.first_city
                child = Node([x for x in node.unvisited if x != city], c, last_city=city, first_city=first_city, parrent=node)
                if child.is_leaf():
                    child.cost += self.cost[city][first_city]
                self.build_tree(child)
                children.append(child)
            node.children = children

    def solve(self):
        root = Node(self.cities, float('inf'))
        self.build_tree(root)
        self.best = root
        self.walk_tree(root)
        self.print_path(self.best)

5. 最长公共子序列 Longest Common Subsequence

给定两个字符串 $X, Y$ ，返回这两个字符串的最长公共子序列的长度。

设有二维数组 $f[i][j]$ 表示 $X$ 的 $i$ 位和 $Y$ 的 $j$ 位前的最长公共子序列长度，则

\begin{aligned} f[1][1] &= S(1, 1) \\f[i][j] &= \max\{f[i-1][j-1] + S(i,j), f[i-1][j], f[i][j-1]\} \end{aligned}

where

S(i, j) = \begin{cases} 1, X[i] = Y[j] \\ 0, X[i] \neq Y[j]\end{cases}

import numpy as np

class LCS:
    def solve(self, X, Y):
        nx = len(X)
        ny = len(Y)
        Z = np.zeros((nx, ny))

        for i in range(0, nx):
            for j in range(0, ny):
                if X[i] == Y[j]:
                    inc = Z[i-1, j-1] if i > 0 and j > 0 else 0
                    Z[i, j] = inc + 1
                else:
                    inc_x = Z[i-1, j] if i > 0 else 0
                    inc_y = Z[i, j-1] if j > 0 else 0
                    Z[i, j] = max(inc_x, inc_y)

        print(Z.max())