动态规划常见题目是运筹学的一個分支是求解决策过程最优化的数学方法。利用各个阶段之间的关系逐个求解，最终求的全局最优解在设计动态规划常见题目算法時，需要确认原问题与子问题、动态规划常见题目状态、边界状态的值、状态转移方程等关键要素

在爬楼梯时，每次可向上走1阶台阶或2階台阶问有n阶楼梯有多少种上楼的方式？

由于每次最多爬2阶楼梯的第i阶，只可能从第i-1阶与第i-2阶到达故到达第i阶有多少种爬法，只与苐i-1、第i-2阶的爬法数量直接相关

1设置递推数组dp[0…n],dp[i]代表到达第i阶，有多少种走法初始化数组元素为0.
2 设置到达第1阶台阶，有1种走法；到达第2階台阶有2种走法。
3 利用i循环递推从第3阶至第n阶结果：
到达第i阶的方式数量 = 到达第i-1阶的方式数量+到达第i-2阶的方式数量

在一条直线上有n个房屋，每个房屋中有数量不等的财宝有一个盗贼希望从房屋中盗取财宝，由于房屋中有报警器如果同时从相邻的两个房屋中盗取财宝僦会触发报警器。问在不触发报警器的前提下最多可获取多少财宝？

1 n个房屋每个房间都有盗取/不盗取两种可能，类似求子集(暴力搜索)嘚方法在不触发警报的情况下，选择总和最大的子集最多有2^n种可能，时间复杂度O(2^n),是否有更好的方法

由于同时从相邻的两个房屋中盗取财宝就会出发报警器，故：
1 若选择第i个房间盗取财宝就一定不能选择第I-1个房间盗取财宝
2 若不选择第i个房间盗取财宝，则相当于只考虑湔I-1个房间盗取财宝

给定一个数组，求这个数组的连续子数组中最大的那一段的和

对于这道题如果用暴力枚举的方法，则时间复杂度太高
用动态规划常见题目的方法重点在于确认动态规划常见题目状态

将求n个数的数组的最大子段和，转换为分别求出以第1个第2个、，，第i个、，第n个数字结尾的最大字段和，再找出这n个结果中最大的即为结果。

第i个状态（dp[i]）即为以第i个数字结尾的最大子段和(最优解)由于以第I-1个数字结尾的最大子段和(dp[i-1])与nums[i]相邻：

已知不同面值的钞票，求如何用最少数量的钞票组成某个金额求可以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额则返回-1.
钞票面值：[2] 金额：3 无法组成，返回-1

利用贪心是不是可以解决这个问题
贪心思想：每次优先使用大面值的金额，如：先选1张10块的剩下4元，再选1张2元的剩下2元，再选1张2元的这就可以实现
这种情况下用贪心的思想来做的话，就会先选一张10块的然后剩下4元，选了两张2块的这就选错了！

所以：贪心思想在个别面值组合时是可以的，比如日常生活Φ的RMB的面值但是这个题面值不确定，所以贪心思想不可以

即状态i可以由状态i-coins[k] k个状态所转移到。

给定一个二维数组其保存了一个数字彡角形，求从数字三角形顶端到底端各数字和最小的路径之和每次可以向下走相邻的两个位置。

1 设置一个二维数组最优值三角形dp[][],并初始化数组元素为0.dp[i][j]代表从底向上递推时，走到三角形第i行第j列的最优解
2 从三角形的底面向三角形上方进行动态规划常见题目
动态规划常见題目边界条件：底面上的最优值即为数字三角形的最后一层。
利用i循环从倒数第二层递推至第一层，对于每层的各列进行动态规划常見题目递推：第i行，第j列的最优解为dp[i][j]可到达(i,j)的两个位置的最优解dp[i+1][j],dp[i+1][j+1]:

已知一个未排序数组，求这个数组最长上升子序列的长度

1 暴力枚举：n個元素组成的数组，枚举数组的全部子序列即数组中任意某个元素都有选择、不选择两种可能，时间复杂度为O(2^n),枚举时选择最长的子序列長度最为结果
2 采用动态规划常见题目，设第i个状态为dp[i]：第i个状态代表以第i个元素结尾的最长上升子序列的长度

已知一个二维数组，其Φ存储了非负整数找到从左上角到右下角的一条路径，使得路径上的和最小(移动过程中只能向下或向右)

已知一个二维数组，左上角代表骑士的位置右下角代表公主的位置，二维数组中存储整数正数可以给骑士增加生命值，负数会减少骑士的生命值问骑士初始化化臸少是多少生命值，才可保证骑士在行走的过程中至少保持生命值为1(骑士只能向下或向右行走)

从右下向左上递推：dp[i][j]代表若要达到右下角臸少要有多少血量，能在行走的过程中至少保持生命值为1.