记忆化搜索(Python题解)

解题思路:

注意事项:

参考代码:

def dfs(n,step):

    for i in range(n//2+1):

        if exist[i]: # 存在直接用

            target=list1[step]

            temp[target]+=temp[i]

        else:

            step+=1

            list1[step]=i

            dfs(i,step)

            # 回溯注意

            exist[i]=1 # 打上标记

            temp[list1[step-1]]+=temp[list1[step]] #step 分解出step+1 回溯前记得累计上

            list1[step]=0

            step-=1

n=eval(input())

exist=list(0 for i in range(1001)) # 判断数是否可以直接获取

temp=list(0 for i in range(1001))

exist[0],temp[0]=1,1

result=[0]

list1=[0 for i in range(1001)]

list1[0]=n

dfs(n,0)

print(temp[n])