课程名称：JavaScript版数据结构与算法
课程章节：第13章 算法设计思想之“动态规划”
主讲老师：lewis
课程内容：
今天学习的内容包括：
13-3 LeetCode：198. 打家劫舍——使用动态规划，把各种可能性分别计算后合并得到解。
13-4 动态规划-章节总结——动态规划的定义以及解题方法。
13-5 【勤于思考，夯实学习成果】阶段思考题——完成对应作业。
课程收获：
198. 打家劫舍
解题思路
- f(k)=从前k个房屋中能偷窃到的最大数额。
- Ak =第k个房屋的钱数。
- f(k)= max(f(k -2)+ Ak, f(k - 1))。
- 考虑使用动态规划。
解题步骤
- 定义子问题： f(k)= max(f(k -2)+ Ak, f(k - 1))。
- 反复执行：从2循环到n，执行上述公式。
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
性能分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n) || O(1)。
章节总结
动态规划是什么
- 动态规划是算法设计中的一种方法。
- 它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。
动态规划的步骤
- 定义子问题。
- 反复执行。
- 合并处理结果。
今天 通过 动态规划 学习了 打家劫舍算法题，今天有种感觉就是算法好像对数学的要求还是有的，明显感觉自己的数学能力不够，理解算法有点吃力，对自己说一句，加油😀~
坚持打卡，坚持学习！明天见💪~