动态规划算法使用特点与例题
动态规划
动态规划题目的特点:
-
计数
-有多少种方式走到右下角
-有多少方式选出k个数使得和是Sum
-
求最大最小值
-从左上角走到右下角路径的最大数字和
-最长上升的子序列长度
-
求存在性
-取石子游戏,先手是否必胜
-能不能选出k个数使得和是Sum
例题:
有三种硬币,分别面值2元,5元和7元,每种硬币都有足够多。若需要买一本书,如何用最少的硬币组合正好付清,不需要对方找钱?
拼出x所需要的最少硬币数为:
-
初始条件:F[0]=0,F[-1]=f[-2]=…=无穷大
-
然后计算F[1],F[2]…
从0开始计算,直到F[27],最终得到F[27]为5。
参考:https://www.bilibili.com/video/BV1xb411e7ww?from=search&seid=1469700049142068914