美团算法笔试最后一题不能用记忆化搜索吗
python，加了@cache注解还是显示爆栈，绷不住了，看数字范围不至于啊
2023-09-02 21:25 北京邮电大学 自然语言处理
关注
全部评论
藏鸿涧 楼主
楼主 北京邮电大学 自然语言处理
原数组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)
相关推荐
查看4道真题和解析 点赞 评论 收藏
分享
