adududu

动态规划

什么是动态规划？

动态规划基本思想

• 拆 拆分成子问题
• 记 记下子问题结果
• 推 根据子问题结果推导出最终的结果

动态规划的题会有什么特点？

• 计数
• 求最大值或最小值
• 求存在性

动态规划三步

• 定义容器。
• 初始化初始值数据。
• 根据状态转移方程写相关代码。

练习题

• 070 爬楼梯 简单

• 053 最大子数组和 中等

• 062 不同路径 中等

• 064 最小路径和 中等

• 198 打家动舍 中等

• 213 打家动舍2 中等

• 322 零钱兑换 中等

• 343 整数拆分 中等

• 005 最长回文子串 中等

• 120 三角形最小路径和 中等

• 279 完全平方数 中等