本章内容
学习动态规划,这是一种解决辣手问题的方法,将问题分解成小问题
学习如何设计问题的动态规划解决方案
背包问题
每个动态规划问题都从网格开始
再加入一个物品如何比如iPhone 2000元 1磅
增加一件更小的商品呢?0.5磅,1000元
当且仅当每个字问题是离散的,即不依赖其他子问题时,动态规划才管用。
最优解可能大致包不满。
动态规划问题的感想
- 动态规划问题帮助你在给定约束条件下找到最优解,只有当问题是离散的才有效果
- 每种动态规划问题都涉及网格
- 每个单元格都是一个子问题
绘制网格
绘图前确定
- 单元格的值是什么
- 如何划分为子问题
- 网格坐标轴是什么
费曼算法
- 将问题写下来
- 好好思考
- 将答案写下来