笔记]动态规划(dynamic programming)
将问题划分为互不相交的子问题，递归求解子问题，再将它们的解组合起来，求出原问题的解。分治算法可能反复的求解某些公共子问题，从而使效率下降，例如用分治法求第n个斐波那契数。算法对每个子问题只求解一次，将其解保存在一个表格中，从而无需反复求解公共子问题。动态规划通常用来求解最优化问题。
1、带备忘录的自顶向下法：执行过程中会保存每个子问题的解。当需要一个子问题的解时，首先检查是否已经保存过此问题的解。如果是，则直接返回保存的值，从而节省计算时间；否则，按通常的方法计算这个子问题
2、自底向上法：将子问题按规模进行排序，按由小到大的顺序进行求解。当求解某个子问题时，其子问题已经求解完毕。
两种方法得到的算法具有相同的渐进运行时间。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。
1、(来源：LeetCode)给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思：从第一个元素开始遍历，Max记录从第一个元素到当前元素的具有最大和的连续子数组的和（自底向上法）。
2、(来源：LeetCode)你是一个专业的小偷，何洁门照艳全集计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
思：自底向上法，由于每一个元素都是正整数，则长度为n的数组，最优解的结构为nums[n]+(n-2)(n-1):nums[n]+(n-2)?(n-1)，(n-2) ，(n-1)代表n-2和n-1的最优解。dp记录当前元素下的最优解，sum记录前一个元素的最优解