前程似锦，一路繁华

https://leetcode-cn.com/problems/triangle/

解法1：动态规划

题目要求O（n）的空间复杂度

所以我们要对状态转移方程进行压缩

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

解法1：贪心

与121题不同，这题可以多次买卖没有对交易次数限制，所以我们可以采用贪心策略，只要赚钱，我们就将股票出售

buyday记录购买日期，i遍历数组，若第i天大于buyday时的价格就让结果值加上这个利润，且更新buyday=i

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解法1：双指针

buy指针记录购买时的价格，i指针遍历数组

若当前价格小于buy价格，则更新buy价格

若当前价格-buy价格大于当前最大利润，则更新当前最大利润

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

解法1：动态规划

1.dp[i][k]表示第i天交易k次所能获得的最大利润

dp[i][k]有两种操作可以求出来，1.第i天什么都不做，那么dp[i][k]=dp[i-1][k].2.第i天选择卖出，既然选择了卖出，那么0-i-1天就要选择一天进行买入，且在买入前已经进行了k-1次交易。

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

解法1：递归

思路：

以abc二叉树为例a是递归中的根节点，b，c是左右子节点（代表递归后的最优解）

题目：https://leetcode-cn.com/problems/distinct-subsequences/

解法1：动态规划

t为目标字符串，s为查找字符串

题目：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

解法1：BFS

思路：

额外空间复杂度O（n）

bfs广度优先搜索

https://leetcode-cn.com/problems/pascals-triangle/

解法1:迭代

思路：

每一行的第一列和最后一列为1，其余列都是上一行对应列和上一行对应列-1之和

题目：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

解法1：迭代

与116题类似

加一个指针变量存当前位置指针

https://leetcode-cn.com/problems/pascals-triangle-ii/

解法1：迭代

要求空间复杂度为k

将118题压缩成只保留当前行

当前行对应元素从右往左更新，当前列=当前列+（当前列-1）对应元素之和