有记忆功能的动态规划看不懂啊。。



经典的动态规划自底向上工作，有些较小子问题的解是不需要的。我们目标是只对必要的子问题求解并且只求一次，所以使用自顶向下的方式，
并维护一个类似自底向上动态规划算法法使用的表格。。。。

这里的自顶向上的方式的意思是什么？  是指求f(n)如有必要再求f（n-1）,以此类推，从最大的问题出发求解吗？？
还有上面最后一张图说只有一个有效单元V(1,2)的值是从表上取到的这是什么意思？？


类似自底向上动态规划算法法使用的表格.。。这句话该怎么理解





#百度##google##微软##C++工程师##算法工程师#
全部评论
你要明白自顶向下是一个递归的过程，原始问题会分解成两个子问题，对于子问题继续递归求解。而备忘录法的实质就是"每次计算后，我们会把计算结果保存在表格中"，那么当我们遇到一个子问题，我们可以先在表格查找这个子问题是否存在(伪代码的第一句if F[i][j]<0)，如果不存在就计算这个子问题，如果存在，F[i][j]里存的就是这个子问题的解，直接跳转到最后一行return F[i][j]。然后考虑这个自顶而下的过程F[4][5]需要求解F[3][3]和F[3][5]，这两个子问题继续递归下去，你发现，只有F[1][2]这个子问题，需要求解两遍，第一遍继续求解子问题，第二遍查找！而这次查找也带来了效率的提升，随着表格的表大，查找的比例会更大
点赞 回复 分享
发布于 2015-12-08 11:48
他说的应该是记忆搜索和动态规划。从某种层面上讲都是减少重复计算。从经验上讲一般动态规划可以过的题你用记忆搜索也没问题。
点赞 回复 分享
发布于 2016-09-01 14:25
点赞 回复 分享
发布于 2015-12-08 16:19
我觉得看起来应该是自顶向下？
点赞 回复 分享
发布于 2015-12-07 22:26

相关推荐

头像
03-22 20:56
华北电力大学（保定） Java
蚂蚁集团-AI Coding笔试
使用在线IDE，根据一个readme文件，写出一个完整的项目。readme如下：智能安全邮箱设计题目目标在本地环境实现一个“可用&nbsp;+&nbsp;可测&nbsp;+&nbsp;有安全设计”的邮箱系统，包含服务端与客户端，并引入基础智能能力。总体约束不可直接使用成熟开源邮箱系统库作为核心实现。可使用通用网络库与基础加密库，但需说明用途。所有功能需提供可复现测试步骤和结果。必做功能1.&nbsp;服务器管理实现&nbsp;server&nbsp;进程，负责接收、存储、分发邮件。测试要求：同时运行两个服务器，模拟两个隔离域名的邮箱系统。两个系统之间可互相发信。两个系统存储应逻辑隔离（不可直接读写对方用户数据目录）。2.&nbsp;客户端管理实现&nbsp;client&nbsp;进程，负责...
点赞 评论 收藏
分享
头像
03-22 13:55
已编辑
华东师范大学 算法工程师
美团算法笔试 没活硬整
出大数据结构题何意味，而且是最无聊的拼板子题，还必须默写板子，这都不是给ACM选手做的题了，这是给OI选手做的题，你招中学生去吧。选择题8题&nbsp;一共20分编程题4题&nbsp;一共80分第一题给定一个数组，将这个数组复制1e9次得到一个超大的数组，问这个新数组的最长严格上升子序列的长度，很明显可以每次复制都只选一个元素，所以答案就是数组中有多少不同的数，直接sort后unique即可第二题要用numpy、pandas、scikit-learn实现单层GRU前向传播，没时间做了第三题给定一个数组，要求将数组切割成任意个子数组，使得每一个子数组中的众数*数组长度之和最小，这题直接dp即可，用unordered...
美团笔试
点赞 评论 收藏
分享
03-13 10:36
河南师范大学 嵌入式软件开发
点赞 评论 收藏
分享
03-21 23:23
中国科学院大学 人工智能
绷不住了，好像不知不觉就作弊了
一开始签了个AI&nbsp;coding什么的，当时想欸这么好可以用AI？（似乎那个AI&nbsp;coding是ai面试？）然后再看又是切屏不计入，又是允许本地IDE，干脆直接chatgpt启动了出来和大家讨论发现好像不能用AI上小红书搜发现这么干的不是少数，尤其是本地IDE直接是cursor和trae的而且发现这个问题去年秋招就有人问过，更离谱的是当时有的人问HR，有的HR说可以有的说不可以现在发了邮件去问招聘团队了，感觉是细则没写清楚要是直接说不能用不如直接签到题走人更省时间
二十岁的编程男神王大...：牛逼，四道题都ai出来无敌了，这个太难绷了，这还考鸡毛，直接复制题目发给cursor
校招笔试
点赞 评论 收藏
分享
03-20 10:32
科大讯飞_教育BG_后端开发(准入职员工)
点赞 评论 收藏
分享
评论
2
收藏
分享

招聘动态

查看更多

鹏芯微

2026届校园招聘

米哈游2026校园招聘

应届生春招&全年实习生专项

莉莉丝

2026春季校园招聘

招商银行·招银网络科技

2026届校园招聘

麦吉太文

2026校园招聘

小米集团

2026届春季校园招聘

厦门银行

2026届春季校园招聘

联想

26届补录&27届暑期实习

携程集团

2026年春季校园招聘

AI网申助手

网申字段一键填写

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 春招至今，你的战绩如何？ #
11036次浏览 94人参与
# 你的实习产出是真实的还是包装的？ #
1950次浏览 42人参与
# 巨人网络春招 #
11364次浏览 223人参与
# 军工所铁饭碗 vs 互联网高薪资，你会选谁 #
7636次浏览 43人参与
# 简历第一个项目做什么 #
31741次浏览 341人参与
# 重来一次，我还会选择这个专业吗 #
433542次浏览 3926人参与
# MiniMax求职进展汇总 #
24114次浏览 309人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
187199次浏览 1122人参与
# 牛客AI文生图 #
21446次浏览 238人参与
# 不考虑薪资和职业，你最想做什么工作呢？ #
152445次浏览 888人参与
# 研究所笔面经互助 #
118964次浏览 577人参与
# 简历中的项目经历要怎么写？ #
310354次浏览 4219人参与
# AI时代，哪些岗位最容易被淘汰 #
63815次浏览 828人参与
# 面试紧张时你会有什么表现？ #
30510次浏览 188人参与
# 你今年的平均薪资是多少？ #
213130次浏览 1039人参与
# 你怎么看待AI面试 #
180126次浏览 1258人参与
# 高学历就一定能找到好工作吗？ #
64331次浏览 620人参与
# 你最满意的offer薪资是哪家公司？ #
76539次浏览 374人参与
# 我的求职精神状态 #
448122次浏览 3129人参与
# 正在春招的你，也参与了去年秋招吗？ #
363507次浏览 2638人参与
# 腾讯音乐求职进展汇总 #
160672次浏览 1112人参与
# 校招笔试 #
471165次浏览 2964人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务