贪心与动态规划入门
数据结构与算法基础#Python全栈#第五阶段#数据结构与算法基础#贪心与动态规划入门约 535 字 · 2 分钟阅读
追问显示点击任意追问卡片可收起 / 展开
贪心与动态规划的基本思路有什么区别？
追问 局部最优为什么不一定产生全局最优？怎样用反例检验直觉方案？
动态规划的状态、转移与初始条件分别是什么？
追问 求 n 阶台阶的走法，每次走 1 或 2 阶时，如何定义状态与小规模样例？
直接递归计算斐波那契数，为什么会重复计算？
追问 记忆化、迭代与滚动变量分别如何改变时间和空间成本？
记忆化递归与自底向上计算如何选择？
追问 需要的状态范围、递归深度、缓存和遍历顺序有什么影响？
状态压缩为什么需要考虑依赖顺序？
追问 如果后一个状态仍需要旧值，原地覆盖可能导致什么错误？
任意币值的最少硬币数问题，能否总先取最大面额？
追问 币值
[1, 3, 4]、金额 6 能说明什么？无限使用与不可达情况如何定义 DP？如何求整数列表的最大连续子数组和？
追问 规定非空输入且结果至少包含一项；全负数时为什么不能默认返回 0？
如何选择最多个互不重叠的活动？
追问 活动采用
[start, end) 且 start < end；为什么按结束时间选择比按开始时间更合适？0/1 背包与物品可重复选择的问题有什么区别？
追问 先假设重量与价值为正整数；一维 DP 的容量遍历方向如何影响“重复使用”？
怎样验证一个 DP 或贪心方案没有遗漏状态？
追问 手算小样例、穷举对照、无法完成的输入和临界规模如何组合验证？