动态规划

动态规划题目特点

• 计数型动态规划 有多少种方式可以走到右下角 有多少种方法可以选出k个数使和为sum
• 求最大值最小值动态规划 从左上角走到右下角路径的最大数字和 最长上升子序列的长度
• 求存在性动态规划 取石头游戏，判断先手是否赢 能不能选出k个数，使其和为sum

动态规划解题步骤

实例

求最少硬币组合问题

假如你有三枚硬币面值分别是2，5，7元，每种硬币无限多，买一本书需要27元，如何用最少的硬币正好付清这本书，不需要找钱。

Dijkstra（迪杰斯特拉）算法