记录得物笔试算法题

考试的时候没有全部做出来，复盘一下总结题目和答案，答案不一定正确，恳请牛友们指正

第一题：n个人，任意两人之间有比赛，第一个人x/x+y 的概率胜，恰好k个人取胜的概率

import math
def cal_prob(n,k,an):
	if k > 1:
	return 0
	else:
	prob_dic = {}
	for i in range(n):
		prob_dic[i] = [an[i]/(an[i] + an[x]) for x in range(n) if x != i]
	sum_prob = sum([math.prod(prob_dic[j]) for j in range(n)])
	if k == 1:
		return round(sum_prob, 2)
	else:
		return round(1-sum_prob, 2)
				   
	 

第二题：最长合法前缀：

解法来自“春秋招笔试突围”

def find_long(s):
	count = 0
	max_len = 0
	for i in range(len(s)):
		if s[i] == '(':
			count += 1
		else:
			if count == 0:
				break
			count -= 1
		if count == 0:
			max_len = i + 1
	return max_len

第三题：生成字符串，+1个字符成本p，+1个子串成本q，求最小生成的成本

（不确定代码是否是对的）

def min_cost(s, p, q):
	n = len(s)
	dp = [0] * (n+1）
	for i in range(1, n+1):
		dp[i] = dp[i-1] + p
		for j in range(i-1, 0, -1):
			if s[j:i] in s[:j]:
				dp[i] = min(dp[i], dp[j] + q)
	return dp[n]