首页 > 代码库 > Iterable<T>接口和动态规划
Iterable<T>接口和动态规划
1 Iterable<T>接口
实现这个接口的对象被允许成为 "foreach" 语句的目标。
从代码上看,Iterable只是包装了一个Iterator<T> iterator();但这样包装一下后,迭代器就变成可迭代的了。
1.5后,引入了foreach,collections都实现了Iterable<T>接口。如果是实现Iterator<T>,则对List list的遍历会是list.next(),这就需要在list内部维护一个位置指针,将这个指针放在抽象出的迭代器中,是合理的。
2 动态规划
动态规划的基本思想是将待求解的问题分解为若干个子问题,按顺序求解子问题。前一子问题的解,为后一子问题的求解提供了有用的信息。
动态规划算法和分治法的基本思想比较类似,区别在于动态规划解决的问题可以分解为重叠子问题,而分治法则可以分解为独立的子问题。即动态规划是纵向分解,而分治法是横向分解。
动态规划算法的做法与一般的递归算法相反:一般来说,递归的计算方式是自顶向下;而动态规划则是自底向上。好处是,已经求解过的问题会保存,避免了重复计算。
由于动态规划是纵向切分,其适用条件比较严格,需要满足:
- 无后效性。未来与过去无关。父阶段的解不会受子阶段影响。从状态图上看,该条约束了一个无回路的状态图。该条件的物理意义在于,原问题可以纵向分解为多个子问题(阶段)。
- 最优化原理。一个最优化策略的子策略总是最优的。满足此条件,即可以把问题分解为若干个可能解及每个解对应的子问题。该条件的物理意义在于纵向分解的子问题,独立求得的解是最优解。(貌似说反了,待修正)
动态规划(Dynamic Programming),这里的规划,是查表的意思。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。