目录

1.1226. 包子凑数 - AcWing题库

2.1070. 括号配对 - AcWing题库

3.1078. 旅游规划 - AcWing题库

4.118. 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)

5.119. 杨辉三角 II - 力扣（LeetCode） (leetcode-cn.com)

---

1.1226. 包子凑数 - AcWing题库

def gcd(a,b):
    if a<b:
        a,b=b,a
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
N=10001
a=[0]
for i in range(n):
    a.append(int(input()))
a.sort()
flag=False
x=gcd(a[1],a[2])
for i in range(2,n+1):
    x=gcd(x,a[i])
if x!=1:
    print("INF")
else:
    dp=[[False for i in range(N)]for j in range(n+1)]
    for i in range(1,n+1):
        for j in range(N):
            if j==0:
                dp[i][j]=True
            else:
                dp[i][j]=dp[i-1][j]
                if j>=a[i]:
                    dp[i][j]=(dp[i][j] or dp[i][j-a[i]])
    print(dp[-1].count(False))

2.1070. 括号配对 - AcWing题库

注意这个0和1<<31的位置

s=input()
n=len(s)
dp=[[0 for i in range(n)]for j in range(n)]
for len in range(1,n+1):
    for l in range(n):
        r=l+len-1
        if r>=n:
            break
        else:
            if len==1:
                dp[l][r]=1
            else:
                dp[l][r]=1<<31
                for k in range(l,r):
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r])
                if (s[r]==']' and s[l]=='[') or (s[r]==')' and s[l]=='('):
                    dp[l][r]=min(dp[l][r],dp[l+1][r-1])
                dp[l][r]=min(dp[l][r],1+dp[l+1][r],1+dp[l][r-1])
print(dp[0][n-1])

3.1078. 旅游规划 - AcWing题库

def dfs_d(u,father):
    global maxlength
    for i in tree[u]:
        if i !=father:
            dfs_d(i,u)
            d=1+d1[i]
            if d>d1[u]:
                d2[u]=d1[u]
                d1[u]=d
                p1[u]=i
            elif d>d2[u]:
                d2[u]=d
    maxlength=max(maxlength,d1[u]+d2[u])
def dfs_u(u,father):
    for i in tree[u]:
        if i!=father:
            up[i]=up[u]+1
            if p1[u]==i:
                up[i]=max(up[i],d2[u]+1)
            else:
                up[i]=max(up[i],d1[u]+1)
            dfs_u(i,u)

n=int(input())
tree=[[]for i in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    tree[x].append(y)
    tree[y].append(x)
maxlength=-1
d1=[-1 for i in range(n)]
d2=[-1 for i in range(n)]
p1=[-1 for i in range(n)]
up=[-1 for i in range(n)]
dfs_d(0,-1)
dfs_u(0,-1)
for i in range(n):
    martix=[d1[i],d2[i],up[i]]
    martix.sort()
    if martix[1]+martix[2]==maxlength:
        print(i)

4.118. 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans=[]
        for i in range(numRows):
            if i==0:
                ans.append([1])
            elif i==1:
                ans.append([1,1])
            else:
                cur=[1]
                for j in range(1,i):
                    cur.append(ans[-1][j]+ans[-1][j-1])
                cur.append(1)
                ans.append(cur)
        return ans

5.119. 杨辉三角 II - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        pre=[]
        cur=[]
        for i in range(rowIndex+1):
            if i==0:
                cur.append(1)
            elif i==1:
                cur.append(1)
                cur.append(1)
            else:
                cur.append(1)
                for j in range(1,i):
                    cur.append(pre[j]+pre[j-1])
                cur.append(1)
            pre=copy.deepcopy(cur)
            cur.clear()
        return pre