algorithm

################斐波那契数列#######################

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    if n < 1:
        return -1
    return fibonacci(n-1) + fibonacci(n-2)


def fibonacci_memo(n):
    memo = [0] * (n + 1)

    def fibonacci(n):
        if n == 1 or n == 2:
            return 1
        if n < 1:
            return -1
        if memo[n] != 0:
            return memo[n]
        memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
        return memo[n]
    return fibonacci(n)


def fibonacci_dp_table(n):
    if n < 1:
        return -1
    dp_table = [0] * (n+1)
    dp_table[1], dp_table[2] = 1, 1
    for i in range(3, n+1):
        dp_table[i] = dp_table[i-1] + dp_table[i-2]
    return dp_table[n]


print(fibonacci(20))
print(fibonacci_memo(20))
print(fibonacci_dp_table(20))

######################最长递增子序列##############

# 时间复杂度N**2
test = [4, 6, 7, 9, 1, 2, 3, 2]

# base case
dp = [1] * len(test)

# 状态转移
total = 0
for i in range(len(test)):
    for j in range(i):
        total += 1
        print(i, j)
        if test[j] < test[i]:
            dp[i] = max(dp[i], dp[j]+1)

result = max(dp)
print(total)
print(result)

######################求两个字符串的最长公共子串##############

def lcs(str1, str2):
    m, n = len(str1), len(str2)
    dp = (m*[0])*n
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    return dp[m][n]

###############最小编辑距离###################

def min_distance(s1, s2):
    # 暴力解法
    def dp(i, j):
        # 返回值就是s1[0..i] 和 s2[0..j]的最小编辑距离
        if i == -1:
            return j+1
        if j == -1:
            return i+1
        if s1[i] == s2[j]:
            return dp(i-1, j-1)  # 什么都不做
        else:
            return min(
                # 递归
                dp(i, j-1) + 1,  # 插入
                dp(i-1, j) + 1,  # 删除
                dp(i-1, j-1) + 1  # 替换
                )
    return dp(len(s1)-1, len(s2)-1)

def min_distance2(s1, s2):
    # 动态规划解法
    memo = dict()  # 备忘录
    def dp(i, j):
        # 先查备忘录，避免重复计算
        if (i, j) in memo:
            return memo[(i, j)]
        # base case
        if i == -1:
            return j+1
        if j == -1:
            return i + 1
        if s1[i] == s2[j]:
            memo[(i, j)] = dp(i-1, j-1)
        else:
            memo[(i, j)] = min(
                # 递归
                dp(i, j - 1) + 1,  # 插入
                dp(i - 1, j) + 1,  # 删除
                dp(i - 1, j - 1) + 1  # 替换
            )
        return memo[(i, j)]
    return dp(len(s1) - 1, len(s2) - 1)


def min_distance3(s1, s2):
    # dp table 解法
    import numpy as np
    m, n = len(s1), len(s2)
    dp = np.zeros((m+1, n+1))
    # base case
    for i in range(1, m+1):
        dp[i][0] = i
    for j in range(1, n+1):
        dp[0][j] = j
    # 自底向上求解
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(
                    # 递归
                    dp[i][j - 1] + 1,  # 插入
                    dp[i-1][j] + 1,  # 删除
                    dp[i-1][j-1] + 1  # 替换
                )
    return int(dp[m][n])


x = min_distance("abcd", "abcde")
y = min_distance3("abcd", "abcde")
print(y)

##########最长回文子序列##########################

# 子序列 vs 子串，前者是不连续序列，后者是连续的；求解时一般子序列更困难
# 求最长回文子序列
import numpy as np
def long_palindrome_subseq(s):
    n = len(s)
    dp = np.zeros((n, n))
    # base case
    for i in range(n):
        dp[i][i] = 1
    # 反向遍历保证正确的状态转移
    for i in range(n-2, -1, -1):
        for j in range(i+1, n):
            # 状态转移方程
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]


s = "kfdhjaklnfl"
res = long_palindrome_subseq(s)
print(res)

##############背包问题###########################

# 0-1背包问题

import numpy as np
def knapsack(N, W, wt, val):
    # N代表物品数量， W代表背包能装的重量， wt代表每个物品的重量，
#  val代表每个物品的价值
    dp = np.zeros((N+1, W+1))
    for i in range(N):
        dp[i][0] = 0
    for j in range(W):
        dp[0][j] = 0
    for i in range(1, N+1):
        for j in range(1, W+1):
            # print(i, j, wt[i-1])
            if j - wt[i-1] < 0:
                # 背包总体容量<当前物品重量，只能选择不装入背包
                dp[i][j] = dp[i-1][j]
            else:
                # 装入或不装入背包
                dp[i][j] = max(
                    dp[i-1][j-wt[i-1]]+val[i-1],   # 把物品装进背包， =在不装i物品的情况下最大价值+i物品价值
                    dp[i-1][j]  # 不把i物品装进背包
                )
    return dp


dp = knapsack(3, 4, [2,1,3], [4, 2, 3])
print(dp[3][4])

# 子集背包问题，输入一个只包含正整数的非空数组nums，
# 判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等
def can_partition(nums):
    total = sum(nums)
    n = len(nums)
    if total % 2 != 0:
        return False
    bi_total = int(total / 2)
    dp = np.zeros((n+1, bi_total+1))
    dp = np.array(dp, dtype=bool)
    for i in range(1, n+1):
        dp[i][0] = True  # 背包没有空间的时候就是装满了
    for i in range(1, n+1):
        for j in range(1, bi_total+1):
            if j - nums[i-1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
    return dp[n][bi_total]
def can_partition2(nums):
    total = sum(nums)
    n = len(nums)
    if total % 2 != 0:
        return False
    bi_total = int(total / 2)
    dp = np.zeros(bi_total+1)
    dp = np.array(dp, dtype=bool)
    dp[0] = True  # 背包没有空间的时候就是装满了
    for i in range(n):
        for j in range(bi_total, 0, -1):
            if (j - nums[i]) >= 0:
                dp[j] = dp[j] or dp[j-nums[i]]
    return dp[bi_total]
res1 = can_partition([1,5,11,5])
res2 = can_partition2([1,5,11,5])
print(res1, res2)
# 给定K种面值的硬币，面值分别为c1, c2, ..., ck， 每种硬币的数量无限，
# 再给一个总金额amount， 最少需要几枚硬币凑出这个金额，
# 如果不可能凑出，算法返回-1。

def coin_change(coins, amount):
    dp = [amount+1] * (amount+1)
    dp[0] = 0
    for i in range(amount+1):
        for coin in coins:
            if (i - coin) < 0:
                continue
            dp[i] = min(dp[i], 1+dp[i-coin])
    if dp[amount] == (amount+1):
        return -1
    else:
        return dp[amount]
res = coin_change([1], 13)
print(res)
# 完全背包问题，零钱兑换ii,给定不同面额的coins和一个总金额amount，
# 写一个函数来计算可以凑成总金额的硬币组合数，
# 假设每一种面额的金币有无限个。
def change(amount, coins):
    if len(coins) == 1 and coins[0] != amount:
        return 0
    length = len(coins)
    dp = np.zeros((length+1, amount+1))
    for i in range(length+1):
        dp[i][0] = 1
    for i in range(1, length+1):
        for j in range(1, amount+1):
            if (j - coins[i-1]) >= 0:
                dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[length][amount]
res = change(10, [1, 2, 5])
print(res)

##################vivo1###################

# 一个完整的软件项目往往会包含很多由代码和文档组成的源文件。
# 编译器在编译整个项目的时候，可能需要按照依赖关系来依次编译每个源文件。
# 比如，A.cpp 依赖 B.cpp，那么在编译的时候，编译器需要先编译 B.cpp，才能再编译 A.cpp。
# 假设现有 0，1，2，3 四个文件，0号文件依赖1号文件，1号文件依赖2号文件，3号文件依赖1号文件，则源文件的编译顺序为 2,1,0,3 或 2,1,3,0。
# 现给出文件依赖关系，如 1,2,-1,1，表示0号文件依赖1号文件，1号文件依赖2号文件，2号文件没有依赖，3号文件依赖1号文件。
# 请补充完整程序，返回正确的编译顺序。注意如有同时可以编译多个文件的情况，按数字升序返回一种情况即可，比如前述案例输出为：2,1,0,3

import heapq
def compileSeq(input_):
    # write code here
    nums = [int(x) for x in input_.split(",")]
    n = len(nums)
    in_degree = [0] * n
    relation = [set() for _ in range(n)]
    res = []
    que = []
    # 获取
    for i in range(n):
        if nums[i] != -1:
            in_degree[i] += 1
            relation[nums[i]].add(i)
    print(in_degree)
    print(relation)
    for i in range(n):
        if in_degree[i] == 0:
            que.append(i)

    while que:
        cur = que[0]
        que = que[1:]
        res.append(cur)
        for idx in relation[cur]:
            in_degree[idx] -= 1
            if in_degree[idx] == 0:
                heapq.heappush(que, idx)
    string = ",".join([str(x) for x in res])
    return string


def compileSeq2(input_):
    a = list(map(int, input_.split(',')))
    n = len(a)
    dic = {}
    sq = []
    sq1 = []
    for i in range(n):
        dic[i] = a[i]
    for i in range(n):
        if dic[i] == -1:
            sq.append(i)
    while len(sq) < n:
        for i in range(n):
            if dic[i] in sq and i not in sq:
                sq.append(i)
                break
    for i in range(n):
        sq1.append(str(sq[i]))
    a = ','.join(sq1)
    return a
print(compileSeq2("1,2,-1,1"))

#####################动态规划-以最小插入次数构造回文串###########

# 回文字符串就是正读和反读都一样的字符串，
# 如“viv”、“nexen”、“12321”、“qqq”、“翻身把身翻” 等。
# 给定一个非空字符串 str，在最多可以删除一个字符的情况下请
# 编程判定其能否成为回文字符串；如果可以则输出首次删除一个
# 字符所能得到的回文字符串，如果不行则输出字符串 "false" 。

import copy
def is_palinoric(string):
    flag = True
    length = len(string)
    for i in range(length//2):
        if string[i] != string[-i-1]:
            flag = False
            break
    return flag

def after_del_is_palinoric(string):
    str_list = list(string)
    if is_palinoric(string):
        print(string)
    else:
        for idx, _ in enumerate(string):
            tmp_list = copy.deepcopy(str_list)
            tmp_list.pop(idx)
            candidate = "".join(tmp_list)
            if is_palinoric(candidate):
                return candidate
        else:
            return False
string = "abab"
res = after_del_is_palinoric(string)
print(res)

################vivo3#####################

# vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，
# 为了保障用户体验，
# 运营同学将按运营流程和规范对其做出分析评估。
#经过初步了解后分析得知，
# 该游戏的地图可以用一个大小为 n*n 的矩阵表示，
#每个元素可以视为一个格子，
# 根据游戏剧情设定其中某些格子是不可达的
#(比如建筑、高山、河流或者其它障碍物等)，
# 现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，
#以协助运营小伙伴评估该游戏的可玩性和上手难度。

def dfs(x, y, grid, endx, endy, visited, count):
    if x < 0 or y < 0 or x >= len(grid) or y >= len(grid) or grid[x][y] in "#@" \
            or (visited[x][y] != 0 and visited[x][y] <= count):
        return
    visited[x][y] = count
    if x == endx and y == endy:
        return
    dfs(x, y + 1, grid, endx, endy, visited, count + 1)
    dfs(x, y - 1, grid, endx, endy, visited, count + 1)
    dfs(x - 1, y, grid, endx, endy, visited, count + 1)
    dfs(x + 1, y, grid, endx, endy, visited, count + 1)


if __name__ == "__main__":
    n = int(input())
    [starty, startx, endy, endx] = list(map(int, input().split()))
    road = []
    for i in range(n):
        road.append(list(input()))
    visited = [[0] * n for _ in range(n)]
    dfs(startx, starty, road, endx, endy, visited, 1)
    print(visited[endx][endy] - 1)

####################二分查找法########################

test = [1, 2, 3, 2, 4, 6, 7, 9]
search_ele = 9
left = 0; right = len(test)
test.sort()
print(test)
while left < right:
    mid = (left+right)//2
    if search_ele < test[mid]:
        right = mid - 1
    elif search_ele > test[mid]:
        left = mid + 1
    else:
        print(mid)
        break

##################动规之正则表达式################

##################动规之高楼扔鸡蛋################

##################动规之戳气球问题################

##################数据结构之二叉搜索树################

##################数据结构之二叉搜索树################