class Solution {public://记录四个方向int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int n, m;//深度优先搜索，返回最大单元格数int dfs(vector > &matrix, vector > &dp, int i, int j) {if(dp[i][j] != 0)return dp[i][j];dp[i][j]++;for(int k = 0; k < 4; k++){int nexti = i + dirs[k][0];int nextj = j + dirs[k][1];//判断条件if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j])dp[i][j] = max(dp[i][j], dfs(matrix, dp, nexti, nextj) + 1);}return dp[i][j];}int solve(vector >& matrix) {//矩阵不为空if(matrix.size() == 0 || matrix[0].size() == 0)return 0;int res = 0;n = matrix.size();m = matrix[0].size();//i，j处的单元格拥有的最长递增路径vector > dp (n, vector  (m));for(int i = 0; i < n; i++)for (int j = 0; j < m; j++)//更新最大值res = max(res, dfs(matrix, dp, i, j));return res;}};

class Solution {public:int fun(string& s, int begin, int end){//每个中心点开始扩展while(begin >= 0 && end < s.length() && s[begin] == s[end]){begin--;end++;}//返回长度return end - begin - 1;}int getLongestPalindrome(string A) {int maxlen = 1;//以每个点为中心for(int i = 0; i < A.length() - 1; i++)//分奇数长度和偶数长度向两边扩展maxlen = max(maxlen, max(fun(A, i, i), fun(A, i, i + 1)));return maxlen;}};

class Solution {public:int editDistance(string str1, string str2) {int n1 = str1.length();int n2 = str2.length();//dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离vector > dp(n1 + 1, vector(n2 + 1, 0));//初始化边界for(int i = 1; i <= n1; i++)dp[i][0] = dp[i - 1][0] + 1;for(int i = 1; i <= n2; i++)dp[0][i] = dp[0][i - 1] + 1;//遍历第一个字符串的每个位置for(int i = 1; i <= n1; i++)//对应第二个字符串每个位置for(int j = 1; j <= n2; j++){//若是字符相同，此处不用编辑if(str1[i - 1] == str2[j - 1])//直接等于二者前一个的距离dp[i][j] = dp[i - 1][j - 1];else//选取最小的距离加上此处编辑距离1dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;}return dp[n1][n2];}};

class Solution:def rob(self , nums: List[int]) -> int:#dp[i]表示长度为i的数组，最多能偷取多少钱dp1 = [0 for i in range(len(nums) + 1)]#选择偷了第一家dp1[1] = nums[0]#最后一家不能偷for i in range(2, len(nums)):#对于每家可以选择偷或者不偷dp1[i] = max(dp1[i - 1], nums[i - 1] + dp1[i - 2])res = dp1[len(nums) - 1];#第二次循环dp2 = [0 for i in range(len(nums) + 1)]#不偷第一家dp2[1] = 0#可以偷最后一家for i in range(2, len(nums) + 1):#对于每家可以选择偷或者不偷dp2[i] = max(dp2[i - 1], nums[i - 1] + dp2[i - 2])#选择最大值return max(res, dp2[len(nums)])

最多可以买入卖出2次，那实际上相当于它的状态多了几个，对于每天有到此为止的最大收益和持股情况两个状态，持股情况有了5种变化，我们用：dp[i][0]dp[i][0]dp[i][0]表示到第i天为止没有买过股票的最大收益dp[i][1]dp[i][1]dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益dp[i][2]dp[i][2]dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益dp[i][3]dp[i][3]dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益dp[i][4]dp[i][4]dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益class Solution {public:int maxProfit(vector& prices) {int n = prices.size();//初始化dp为最小vector > dp(n, vector(5, -10000));//第0天不持有状态dp[0][0] = 0;//第0天持有股票dp[0][1] = -prices[0];//状态转移for(int i = 1; i < n; i++){dp[i][0] = dp[i - 1][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}//选取最大值，可以只操作一次return max(dp[n - 1][2], max(0, dp[n - 1][4]));}};

class Solution {public:int maxProfit(vector& prices) {int n = prices.size();//dp[i][0]表示某一天不持股到该天为止的最大收益//dp[i][1]表示某天持股，到该天为止的最大收益vector > dp(n, vector(2, 0));//第一天不持股，总收益为0dp[0][0] = 0;//第一天持股，总收益为减去该天的股价dp[0][1] = -prices[0];//遍历后续每天，状态转移for(int i = 1; i < n; i++){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}//最后一天不持股，到该天为止的最大收益return dp[n - 1][0];}};

//  结点1->next结点2->next结点3//    |          |//  pHead       temp(保存pHead的后继结点)//变为://  结点1next<-结点2->next结点3//    |          |         |//  preNode     pHead     temp////需要4步: 第1步：保存pHead的后继结点；//         第2步：将结点2的后继变为结点1;//         第3步：preNode指针后移//         第4步：pHead指针后移//循环以上4步，至到pHead为空即可结束循环struct ListNode* ReverseList(struct ListNode* pHead ) {struct ListNode* preNode = NULL;struct ListNode* temp = NULL;while(pHead != NULL)            //至到pHead为空即可结束循环{temp = pHead->next;       //第1步pHead->next = preNode;   //第2步preNode = pHead;        //第3步pHead = temp;          //第4步}return preNode;           //返回最开始链表的最后一个结点}

第一天