方格取数（python）

思路

最关键的是分为两类，一类是从上往下和从从左向右取最大值，一类是从下往上和从左往右取最大值，所以每个f[i][j]有两次更新，一次是从下往上，一次是从上往下

python 代码 $O(nm)$

#状态表示：从f[1][1]到f[i][j]向上、向下或向右且下一步向右的所有集合（这里向右是因为，一个位置只有四种放向，列举了上下左三个方向，就只剩向右一个方向了）

#状态计算：s=max(s,f[i][j-1])+shu[i-1][j-1],f[i][j]=max(f[i][j],s)

#这里有个小细节得注意，初始化一定要赋值为无穷大，有个测试点的开头一列为负数，如果赋值为0就会把开头的这一列负数给自动忽略

n,m=map(int,input().split())

shu=[]

for i in range(n):
    shu.append([int(i) for i in input().split()])
f=[[float('-inf') for i in range(m+1)] for j in range(n+1)]
f[1][0]=0
for j in range(1,m+1):
    s=float('-inf')
    for i in range(1,n+1):
        #找到上一个节点的最大值，然后再加上该节点即是这个节点的最大值（新算出的值）
        s=max(s,f[i][j-1])+shu[i-1][j-1]
        #更新f[i][j]，这里会有从上往下，和从下往上两个方向，因此这里要设置一个f[i][j]和新算出的值做一个更新
        f[i][j]=max(s,f[i][j])
    s=float('-inf')
    for i in range(n,0,-1):
        s=max(s,f[i][j-1])+shu[i-1][j-1]
        f[i][j]=max(s,f[i][j])
print(f[n][m])

题目描述

思路：

y总说过了，考虑不重不漏原则，以i为结尾，前面的元素都可能是倒数第二个元素，把全面所有可能是倒数第二个元素考虑进去

这里代码的关键是理解，i，j双重循环，第一重求的以i结尾的，第二重求所有以i结尾的有严格上升子序列的所有集合的最大值,知道f[i]是怎样更新的，f[j]里面存的什么值

python 代码 $O(n^2)$

#状态表示：所有以i结尾的严格单调上升的子序列所有集合
#状态计算：f[i]=f[j]+1和f[i]的一个最大值


N=int(input())

shu=[]

shu=list(map(int,input().split()))

f=[0 for i in range(N+1)]

#以i为结尾的所有严格单调递增子序列的集合的最大值
for i in range(N):
    f[i]=1
    #j遍历的是i前面有那些数严格小于a[i]，并用j不断更新i，以便取得最大值
    #比如1,7，3,5,9  9大于1，就在前面存储1的地方f[0]+1，9大于7，就在前面存储7的地方f[1]+1
    #9大于3，就在前面存储1的地方f[2]+1，9大于5，就在前面存储5的地方f[3]+1，最后f[i]就是这几个数的最大值
    for j in range(i):
        if(shu[j]<shu[i]):
            f[i]=max(f[i],f[j]+1)
res=0
#每次求的是以i结尾的最长子序列的长度，不是全部序列的，因此全部序列需要遍历每个节点的最长子序列的值，求最大
for i in range(N):
    res=max(res,f[i])

print(res)

摘花生（python）

思路

dp算法最关键的是空间换时间，即把每一次计算存储在一个空间中，每次需要的时候找到该位置直接调用，不需要再次计算。

• 动态规划问题要注意两个点：1、不重 2、不漏

• 不重的话，不是必要条件，对于属性为min、max的题目可以忽略，对于属性为count的题目不可以忽略

• 不漏的话，这是必要条件

状态表示：
集合：从…到f[i][j]的所有集合(一般是考虑限制条件那句话，假设第f[i][j]存的是最后一个元素，那么选择或则到达该元素有哪些集合，遵守不重不漏)
属性：题目求的

状态计算：
假如i,j为最后一个点，有几种方案，

C++ 代码 $O(n^2)$

#状态表示：
# 集合：从f[1][1]到f[i][j]的所有集合
# 属性：最大值

#状态计算：
# 假如i,j为最后一个点，有几种方案，
# f[i][j]=f[i-1][j]+f[i][j-1]

T=int(input())
for i in range(T):
    hang=[]
    R,C=map(int,input().split())
    for i in range(R):
        hang.append([int(i) for i in input().split()])

    f=[[0 for m in range(C+1)] for n in range(R+1)]

    for n in range(1,R+1):
        for m in range(1,C+1):
            f[n][m]=max(f[n-1][m],f[n][m-1])+hang[n-1][m-1]

    print(f[R][C])

完全背包问题（python）

思路

01背包和完全背包最大的不同在于01背包只考虑一个物品选还是不选只有两种情况，完全背包需要考虑一个物品需要选几次，1,2,3,4,5,6.....然后再，把得到的等式做一个优化，把j换成v-j可以发现，j的等式后面一串等于v-j后面一串再加一个w

python 代码 $O(n^2)$

n,v=map(int,input().split())

sum=[]

for i in range(n):#存几个数
    sum.append([int(j) for j in input().split()])#把每一个数都强制转换成int类型，并从0开始存

f=[[0 for i in range(v+1)] for j in range(n+1)]



for i in range(1,n+1):
    for j in range(1,v+1):
        f[i][j]=f[i-1][j]
        if(j>=sum[i-1][0]):#sum里面的i需要减一是因为，i从1开始，而sum里面的i从0开始，不减一，数组下标会越界
            f[i][j]=max(f[i][j],f[i][j-sum[i-1][0]]+sum[i-1][1])

print(f[n][v])

朴素算法

思路

每次例举第i个物品在体积为j的限制下选或者不选，保存能够达到的最大的组合，不选即是除掉第i个物品在相同体积下的最大值，选，即是除掉第i个物品和第i个物品的体积在相同体积下i-1个物品价值，最后求一个最大值。

时间复杂度$O(n^2)$

pyhon 代码

n,v=map(int,input().split())

sum=[]

for i in range(n):
    sum.append([int(i) for i in input().split()])


# 初始化，先全部赋值为0，这样至少体积为0或者不选任何物品的时候是满足要求   
f=[[0 for i in range(v+1)] for j in range(n+1)]

#每次例举第i个物品在体积为j的限制下选或者不选，保存能够达到的最大的组合
for i in range(1,n+1):
    for j in range(1,v+1):
        f[i][j]=f[i-1][j]
        if(j>=sum[i-1][0]):# 判断背包容量是不是大于第i件物品的体积
             # 在选和不选的情况中选出最大值
             #1到i中选总体积小于等于j，1到i-1中选总体积小于等于j-vi，
             #这里的i-1是因为sum从0开始存的，这里的i是从1开始存的，因此i要减去1才能和sum里面的数对应
            f[i][j]=max(f[i][j],f[i-1][j-sum[i-1][0]]+sum[i-1][1])


print(f[n][v])

dp优化，都是对代码做等价变形，只能在空间上优化

题目描述

解题思路

从1到n开始遍历，按照题目要求遇到n为偶数，除以二遇到n为基数，3倍加1

时间复杂度(o(n**2)

python 代码

m=int(input())
max=1

for n in range(1,m+1):
    while(n!=1):
        if(n>max):
            max=n
        if(n%2==0):
            n=n//2
        else:
            n=n*3+1
        if(n>max):
            max=n

print(max)

题目描述

python 代码

#递归爆栈，拓扑排序AC
n = int(input())
w = [0]+list(map(int,input().split()))
deg={}
fa={i:[] for i in range(1,n+1)}
f = [i for i in w]
nxt = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    deg[a]=deg.get(a,0)+1
    deg[b]=deg.get(b,0)+1
    fa[b].append(a)
    fa[a].append(b)
queue=[]
for i in deg:
    if deg[i]==1:
        queue.append((i))
visit=set()
while queue:
    u=queue.pop()
    visit.add(u)
    for nxt in fa[u]:
        if nxt not in visit:
            deg[nxt]-=1
            f[nxt]+= max(0,f[u])
            if deg[nxt]==1:
                queue.append((nxt))
res = f[1]
for i in range(2,n+1):
    res = max(f[i],res)
print(res)

密文搜索（python)有错

解题思路

从根号s到long10为底遍历，从后往前，开始循环遍历，直到找出初始数字

C++ 代码

import math
n,s=map(int,input().split(' '))
for i in range(int(math.sqrt(s)),int(math.log10(s)),-1):#缩小范围遍历，从根号s到long10为底遍历，从后往前遍历
    temp=i
    sum=i
    m=i
    for j in range(n):
        temp=2*temp-1
        sum+=temp
        if(sum==s):
            print(m)

这个点过不了
97 2218388550399401452619230609499

题目描述

python 代码

from collections import Counter

string = input().strip()
n, cnt = int(input().split()), 0
password = [input() for _ in range(n)]
for i in password:
    temp = dict(Counter(i))
    for j in range(len(string) - 8 + 1):
        cut = dict(Counter(string[j:j + 8]))
        cnt += 1 if cut == temp else 0
print(cnt)

题目描述

解题思路

这道题与迷宫思路是一样的，运用广度优先的策略，从A点开始遍历，依次遍历该点上下左右，判断该点是否过界，是否已经走过，是否满足题目要求

python 代码

n=int(input())
matrix=[]

for _ in range(n): # 输入数组
    temp=list(map(str,input().split()))
    matrix.append(temp)
path=[[False]*n for _ in range(n)] # 记录该点是否已经走过

def search(x,y,res):
    save=[]
    save.append((x,y,res))#存初始点
    path[x][y]=True

    while save:
        front=save.pop(0)
        x,y,res=front

        if matrix[x][y]=='B':# 遍历到B结束
            return res

        for dx ,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
            nx,ny=dy+x,dx+y
            # 判断，上下，左右移动是否超出边界，该点是否走过，该节点与上一个节点是否相同
            if -1 < ny < n and -1 < nx < n and not path[nx][ny] and matrix[x][y] != matrix[nx][ny]:
                # 该节点设置为走过
                path[nx][ny]=True
                save.append((nx,ny,res+1))
    return -1


for i in range(n):
    for j in range(n):
        if matrix[i][j]=='A':
            print(search(i,j,0))