题目主要信息:  给出一个数组表示连续多日的股票价格 你可以选择在某一天买入股票，在另一天卖出股票，可以最多买入两次卖出两次，但是第二次买入必须在第一次卖出后，且每天只能进行一次操作 假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0  具体思路: 这道题与买卖股票的最好时机（一）的区别在于最多可以买入卖出2次，那实际上相当于它的状态多了几个，对于每天有到此为止的最大收益和持股情况两个状态，持股情况有了5种变化，我们用：  dp[i][0]dp[i][0]dp[i][0]表示到第i天为止没有买过股票的最大收益 dp[i][1]dp[i][1]dp[i][1...

题目的主要信息：  给出一个数组表示连续多日的股票价格 你可以选择在某一天买入股票，在另一天卖出股票，买卖可以有多次机会，但是同一天只能买或者只能卖 假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0  方法一：动态规划 具体做法： 这道题与买卖股票的最好时机（一）的区别在于可以多次买入卖出。 但是对于每天还是有到此为止的最大收益和是否持股两个状态，因此我们照样可以用动态规划。dp[i][0]dp[i][0]dp[i][0]表示第i天不持股到该天为止的最大收益，dp[i][1]dp[i][1]dp[i][1]表示第i天持股，到该天为止的最大收益。  初始状...

题目的主要信息：  给出一个数组表示连续多日的股票价格 你可以选择在某一天买入股票，在另一天卖出股票，买卖都只有一次机会，不能在同一天 假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0 可以看成查找数组中b-a的最大值，其中b必须在a的后面  方法一：动态规划 具体做法： 对于每天有到此为止的最大收益和是否持股两个状态，因此我们可以用动态规划。dp[i][0]dp[i][0]dp[i][0]表示第i天不持股到该天为止的最大收益，dp[i][1]dp[i][1]dp[i][1]表示第i天持股，到该天为止的最大收益。  初始状态： 第一天不持股，则总收益为0...

题目主要信息:  给定一个数组，其中代表每家拥有的钱数 小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷 数组形成环形，第一家与最后一家相邻 求最多能偷到钱数  具体思路: 这道题与打家劫舍（一）比较类似，区别在于这道题是环形，第一家和最后一家是相邻的，既然如此，在原先的方案中第一家和最后一家不能同时取到。 原先的方案是：用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。  初始状态： 如果数组长度为1，只有一家人，肯定是把这家人偷了，收益最大，因此dp[1]=nums[0]dp[1] = nums[0]dp[1]=nums[0...

题目主要信息:  给定一个数组，其中代表每家拥有的钱数 小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷 求最多能偷到钱数  具体思路: 或许有人认为利用贪心思想，偷取最多人家的钱就可以了，要么偶数家要么奇数家全部的钱，但是有时候会为了偷取更多的钱，或许可能会连续放弃两家不偷，因此这种方案行不通。我们依旧考虑动态规划，用dp[i]表示长度为i的数组，最多能偷取到多少钱，只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。  初始状态： 如果数组长度为1，只有一家人，肯定是把这家人偷了，收益最大，因此dp[1]=nums[0]dp[1] = nums[0]dp[1]=nums[0]。...

题目主要信息:  给定一个数组，其中每个元素代表该级楼梯向上爬需要支付的费用，下标从0开始 一旦支付费用，可以任意选择爬一级或是二级 需要求爬到顶楼，即越过数组末尾元素所需要的最小花费 可以从下标为0或是1的台阶开始  具体思路: 可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。  初始状态： 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0. 状态转移： 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：dp[i]=mi...

题目主要信息:   一个正常字符串str，可能为空，只包含小写字母   一个模式串pattern，可能为空，只包含小写字母和‘*’与‘.’   模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）   求str与pattern是否能完全匹配   具体思路: 如果是只有小写字母，那么直接比较字符是否相同即可匹配，如果再多一个'.'，可以用它匹配任意字符，只要对应str中的元素不为空就行了。但是多了'*'字符，它的情况有多种，涉及状态转移，因此我们用动态规划。设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比...

题目主要信息:  给定一个数组，求其中最长的严格上升子序列的长度 子序列是指数组去掉或不去掉元素后的数组，不要求在原本数组中全部相邻，但是在原数组中的相对位置不能改变 严格上升指子序列严格单调递增  具体思路: 要找到最长的递增子序列长度，常用方法是动态规划，用dp[i]dp[i]dp[i]表示到元素iii结尾时，最长的子序列的长度，第一层遍历得到n个长度的子串，第二层遍历该子串求相应到元素iii结尾时的最长递增序列长度，期间维护最大值。  初始条件： 不管如何只要数组不为空，最长递增子序列至少有1个，因此可以初始化dp数组全部为1. 转移方程： 对于每一个到iii结尾的子串，如果遍历过程中遇...

题目的主要信息：  给定一个m*n的矩阵，要求从矩阵的左上角走到右下角的不同路径数量 每次只能往下或者往右走   这道题非常典型，我们可以考虑多种方式。 方法一：递归 具体做法： 首先我们在左上角第一个格子的时候，有两种行走方式：如果向右走，相当于后面在一个(n−1)∗m(n-1)*m(n−1)∗m的矩阵中查找从左上角到右下角的不同路径数；而如果向下走，相当于后面在一个n∗(m−1)n*(m-1)n∗(m−1)的矩阵中查找从左上角到右下角不同的路径数。而(n−1)∗m(n-1)*m(n−1)∗m的矩阵与n∗(m−1)n*(m-1)n∗(m−1)的矩阵都是n∗mn*mn∗m矩阵的子问题，因此可以...

题目主要信息:  给定两个长度可能不同的字符串，可以对第一个字符串增删改字符 求增删改的最少次数，让第一个字符串变成第二个字符串 字符串中只出现大小写字母  具体思路: 把第一个字符串变成第二个字符串，我们需要逐个将第一个字符串的子串最少操作下变成第二个字符串，这就涉及了第一个字符串增加长度，状态转移，那可以考虑动态规划。用dp[i][j]表示从两个字符串首部各自到str1[i]和str2[j]为止的子串需要的编辑距离，那很明显dp[str1.length][str2.length]就是我们要求的编辑距离。（下标从1开始）  step 1：初始条件： 假设第二个字符串为空，那很明显第一个字符串...

题目主要信息:  输入一个数组，其中每个元素代表水桶边界高度 水桶容积为边界较短的一边高度乘上两边界的距离（数组下标表示距离） 求在数组中选取两个边，求最大容积  具体思路: 这道题类似接雨水问题，还是利用了水桶的短板原理，较短的一边控制最大水量，因此直接用较短边长乘底部两边距离就可以得到当前情况下的容积。但是要怎么找最大值呢？可以用双指针+贪心思想：  step 1：优先排除不能形成容器的特殊情况。 step 2：初始化双指针指向数组首尾，每次利用上述公式计算当前的容积，维护一个最大容积作为返回值。 step 3：我们都知道容积与最短边长和底边长有关，双指针向中间靠的情况下，底边长会缩短，因...

题目主要信息:  给定一个整型数组，数组每个元素表示下图所示的每列灰色柱子高度，数值都是非负数 在雨水（图中蓝色部分）不超过边界的情况下，问最多能有多少蓝色的格子 数组以外的区域高度视为0   具体思路: 我们都知道水桶的短板问题，控制水桶水量的是最短的一条板子。这道题也是类似，我们可以将整个图看成一个水桶，两边就是水桶的板，中间比较低的部分就是水桶的底，由较短的边控制水桶的最高水量。但是水桶中可能出现更高的边，比如上图第四列，它比水桶边还要高，那这种情况下它是不是将一个水桶分割成了两个水桶，而中间的那条边就是两个水桶的边。 有了这个思想，解决这道题就容易了，因为我们这里的水桶有两个边，因此可...

题目主要信息:  给定一个矩阵，矩阵中所有元素都是非负整数 需要在矩阵中找到一条最长路径，路径中的元素都是递增的，求其最长长度 查找路径时，只能向上下左右四个方向查找，不能超出边界，且每个格子最多走一次  具体思路: 既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就从上到下从左到右遍历矩阵的每个元素，然后以每个元素都可以作为起点查找它能到达的最长递增路径，然后维护一个最大值。 如何查找以某个点为起点的最长递增路径呢？我们可以考虑递归，因此我们查找递增路径的时候，每次选中路径一个点，然后找到与该点相邻的递增位置，相当于进入这个相邻的点，继续查找递增路径，这就是递...

题目主要信息:  给定一个长度为n的字符串，求其中所有字符的全排列 字符串中可能有重复字符，打印顺序任意 字符串中只包含大小写字母  具体思路: 都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路与有重复数字的全排列类似，只是这道题输出顺序没有要求。但是为了便于去掉重复情况，我们还是应该参照这道数组全排列，优先按照字典序排序，因此排序后重复的字符就会相邻，后续递归找起来也很方便。 依据数组的全排列，使用临时变量去组装一个排列的情况：每当我们选取一个字符以后，就确定了其位置，相当于对字符串中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个...