算法第三章总结
2021-03-20 15:26
阅读：546
标签：总结 思考 连接 使用 路径 推出 一个 合作 题目 根据题目中规定路径都是单向的,且从编号小的地窖通向编号大的地窖，可以确定本题可以使用动态规划解决。首先思考求解时最后一步会做什么——选择最后一个地窖，挖走其中的地雷。 小组合作感觉上课能学到更多。 算法第三章总结 标签：总结 思考 连接 使用 路径 推出 一个 合作 题目 原文地址：https://www.cnblogs.com/xxxxibrgd/p/13911042.html
依据此来推出状态转移方程
设f[i]表示以i地窖为结束点能挖到的最大地雷数。
那么可以写出f[i]=max(f[j]+a[i])
条件是j小于i且j到i有通道连接。
挖地雷的路线可以在每次求f[i]时记住f[i]的值从哪里来，记住j值。
最后根据终点走回去即可。
上一篇：python中的反射
评论
亲，登录后才可以留言！