前言:最近刷剑指offer刷到了动态规划相关的问题,之前没怎么学过,所以特地抽一天时间来学一下,以下为学习的笔记
动态规划
题目类型
1. 计数:
有多少种方式走到右下角
有多少种方法选出k个数使得和为Sum
2. 求最大最小值:
从左上角走到右下角路径的最大数字和
最长上升子序列长度
3. 求存在性:
取石子游戏,先手是否必胜
能不能选出k个数使得和是Sum
解题步骤
确定状态
简单的说,就是解动态规划时需要开一个数组,数组的每个元素f[i]或者f[i][j]代表什么,类似解数学题中,xyz代表什么一样,具体分为下面两个步骤:
研究最优策略的最后一步
化为子问题
转移方程
根据子问题定义直接得到
初始条件和边界情况
初始条件一般都是a[0]、a[1]这种,多看看
边界条件主要是看数组的边界,数组越不越界
计算顺序
大部分从小到大迭代,精髓在于使用之前计算得到的结果
322. 零钱兑换
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总 ...