题目 思路 备注
    爬楼梯 动规； 缓存+递归 同青蛙跳台阶 or Fibonacci数列，f(n) = f(n-1) + f(n-2)
    最大子序和 动规 dp[i] = max( dp[i-1] + nums[i], nums[i] )
    打家劫舍 动规 notStolenTemp = Math.max(notStolen, stolen); //在当前家不偷窃
    stolen = notStolen + nums[i]; //在当前家偷窃时的最高收益
    notStolen = notStolenTemp; //更新不偷窃时的最高收益
    max = max( notStolen , stolen ); //取最大收益
    跳跃游戏 动规：dp[i]表示到达i位置时能够剩余的步数，值为0表示到达i后剩余0步可走了 image.png
    不同路径
    image.png    		 动规：dp[i][j]表示到达i,j位置时的路径总数，则[i,j]=[i-1,j]+[i,j-1] image.png
    零钱兑换
    1. 动规(推荐)：dp[i]表示组成金额i所需硬币的最少个数， 则dp[i] = min(dp[i-c0], dp[i-c1],…dp[i-cn]) + 1; 其中dp[i-c]表示从金额i中除掉其中一个面值为c的金币所对应的最少硬币个数。
    1. 基于N叉树的BFS，树中的节点值表示当前路径下的金额和，已出现过的金额的不用重复建树
    		 动规：image.png
    BFS：image.png
    最长递增子序列 动规：dp[i]表示第[0,i)子数组中的最长子序列的长度，则：在nums[0,i-1)子串中， 如果存在一个下标j, 使得nums[j]<nums[i]，则dp[i] = max(dp[j])+1 image.png
    通配符匹配 ‘?’匹配任意单字符， ‘‘匹配任何0个或多个字符
    基于棋盘法的动态规划， 如右图所示， 在(START,START)位置放一个T，只能在T处时才能继续往右或往下走。 对于棋盘声明一个可以动规的状态表格：int[][] dp = new int[m+1][n+1]， m代表纵轴的模式串， n代表横轴的原串。
    dp[i][j]： 0表示未填充，1表示true，-1表示false， 这里不用boolean数组是为了在过程中记录填充过的单元格，已经填充的不再重复填充，以减少遍历次数。
    其中”    “号可以使得右侧整行填充T， 而“?”可使当前格无脑填充T
    走到最后才代表能成功匹配, 注意处理第0行0列的边界情况    		 示意图与动规代码：
    image.pngimage.png
    正则表达式匹配 ‘.’ 匹配任意单字符，’‘ 匹配0个或多个前一字符
    思路同上一题, 使用棋盘法进行动规， 区别在于需要记录前一个字符：
    1. 对于sc=pc，直接向右下转移
    1. 对于pc = ‘.’ ，则向右下转移
    1. 对于pc=’    ‘，需要记录前一字符的同时，向下转移一位，并向右转移n位直到遇到相同字符的列
    		 关键代码(对*的处理比较复杂，需要实际动手时深入细想)——
    image.png
    乘积最大子数组 动规， 由于数组中存在负数，帮动规过程需要同时维护乘积的最大值和最小值 image.png
    完全平方数 动规：dp[i]表示构成整数i所需要的最少完全平方数， 则转移方程： 动态规划 - 图11， 其中动态规划 - 图12
    注意，动态规划 - 图13的意思就是，令动态规划 - 图14，则动态规划 - 图15表示构成 x所需的最少完全平方数，由于动态规划 - 图16因此，动态规划 - 图17, 这里+1表示在动态规划 - 图18的基础上，多加了一个动态规划 - 图19    		 动规代码：
    image.png
    单词拆分 判断s是否可由指定单词表中的单词组成
    动规：dp[i]表示前i个字符[0~i-1]是否满足切分，则，dp[i]取决于[0~j)的子串结果 以及s[j,i)是否是合法单词, 其中 0<=j<=i-1。 故转移方程为——
    动态规划 - 图21    		 image.png
    单词拆分II 标准回溯法：将字符串s加空格以拆分成单词表中的多个单词构成的句子
    - i从0开始扫描s， j从i开始向右，不断扩展当前子串，如果s[i,j]是一个单词，则加入当前dfs路径结果，直到i到达s的最大长度后，输出完整句子
    - 注意，回溯的过程
    		 image.png
    戳气球 动规：以插气球的方式反向思考：dp[i][j] 表示填满开区间 (i,j) 能得到的最多硬币数(边界条件：i>=j-1)。则转移方程——
    image.png
    最终结果是：dp[0][n+1]    		 因为最终结果是dp[0][n+1]，故代码中注意循环的方向，i要从大到小，j要从小到达：
    image.png
    不含连续1的非负整数 动态规划：(此题难度相当高，思路复杂，具体思路分析参考下方截图)
    dp[i]： 表示长度为i的二进制串的总合法结果数，则 1<=i<=31，(整数虽然是32位，但高位是符号位，可忽略)。
    以在二进制串前增加0或1的方式，讨论可得：dp[i] = dp[i-1]+dp[i-2]
    假设针对 n=10010110 (共8位) 的情况求结果: 累加上各位1应的dp值即可，其中最后还要加一个1: res = dp[7]+dp[4]+dp[2] +1, 这里不加dp[1]，因后续范围内数一定是非法的。
    image.png    		 image.png
    最佳观光组合 动规求两个景点间的最高评分。 动规时要考虑两个维度的最值变量： 一个是局部位置的最值，另一个是全局最值 image.png