美团算法笔试最后一题不能用记忆化搜索吗

python,加了@cache注解还是显示爆栈,绷不住了,看数字范围不至于啊
全部评论
原数组arr先排序,整体思路是从原数组中选。递归函数是dfs(i,j,pre),剪枝暂且不论,i代表当前挑选的目标数arr[i],j表示已选的数,pre是上个选的数,初始化为0。如果pre不为0且arr[j] % pre不为0,说明不能选i,返回dfs(i+1,j,pre).否则返回dfs(i+1,j,pre)+dfs(i+1,j+1,arr[i]) 。函数入口是dfs(0,0,0)
点赞 回复 分享
发布于 2023-09-02 21:36 北京

相关推荐

10-31 14:54
已编辑
门头沟学院 算法工程师
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务