为了降低空间复杂度，本题中dp[i]只和dp[i-1]有关，所以只需要设置一个整型数字即可。profit变量总是在可卖出的时候记录当前最大的卖出利润，也可以理解为一个动态规划问题。

这种思路和官方的解题思路异曲同工，官方解法里面cost是本思路中的dp[i],官方题解中的dp[i]是本思路中的profit.

2.3 数据类型功能函数总结

//none

2.4 java代码

class Solution {public int maxProfit(int[] prices) {int profit=0;if(prices.length==0){return 0;}int dp=prices[0];for(int i=1;iif(prices[i]//更新买入dp=prices[i];}else{//考虑卖出if(prices[i]-dp>profit){profit=prices[i]-dp;}}}return profit;  }
}

3. 剑指 Offer 12. 矩阵中的路径

3.1 题目

给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true
示例 2：输入：board = [["a","b"],["c","d"]], word = "abcd"输出：false提示：m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成

3.2 解题思路

个人思路是从起点开始，每次往四个方向查找，如果都没有合适的则默认一个特定的顺序进行四周的搜索，找到第一个字符之后，继续查找，为了回溯设置一个查找标记的矩阵，和board对应。
结合官方题解，主要解决了我在这个思路中的三个疑问：

• 如何查找到第一个元素：根据官方题解和代码参考，地毯式遍历行列中的元素，如果以某个元素为起点进行搜索得到了最终的结果，则说明矩阵中有字符串，否则则在所有元素遍历完成之后说明矩阵中没有该字符。
• 如何进行遍历和方向搜索：官方题解中给出了DFS深度优先搜索算法，并且使用递归的方式来实现。终止条件设置为越界或者字符不匹配的时候或者查找结束之后，而递归部分分别查找上下左右四个方位，只要有一个方向能走得下去即可。
• 如何进行矩阵元素标记和回溯：为了节省空间，可考虑直接修改矩阵内元素而不是另外开辟一块空间；遍历过的元素则修改为"\0"字符，如果遍历搜索失败，需要回溯，则使用word字符串的当前搜索位置还原被标记的元素。
  DFS算法的递归实现是核心重点。

3.3 数据类型功能函数总结

//二维数组相关操作
int line=array_name.length;//获取行数
int row=array_name[0].length;//获取列数
//字符串相关操作
String.length();//获取字符串长度
String.charAt(index);//获取某个下标的对应字符。

3.4 java代码

class Solution {public boolean exist(char[][] board, String word) {int i=0,j=0,index=0;;int line=board.length;int row=board[0].length;for(i=0;ifor(j=0;jif(dfs(board,word,i,j,0)==true){return true;}}}return false;}boolean dfs(char[][] board,String word,int i,int j,int k){//递归函数if(i >=board.length || j >= board[0].length || j<0||i<0||board[i][j]!=word.charAt(k)){return false;}if(k==word.length()-1){return true;}board[i][j]='\0';boolean re=dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)||dfs(board,word,i,j+1,k+1)||dfs(board,word,i,j-1,k+1);board[i][j]=word.charAt(k);return re;}
}

4. 剑指 Offer 13. 机器人的运动范围

4.1 题目

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？示例 1：输入：m = 2, n = 3, k = 1输出：3示例 2：输入：m = 3, n = 1, k = 0输出：1提示：1 <= n,m <= 1000 <= k?<= 20

4.2 解题思路

和矩阵中的路径类似，需要考虑的是矩阵中的搜索问题，因此还是使用dfs搜索进行矩阵遍历。

终止条件：达到边界或者行坐标和列坐标位数大于k，n和m最大也是二位数。
递归部分：左、右、上、下进行搜索，每次搜索到一个格子，进行格子统计。

后来经过代码测试和题解的提示，首先需要设置访问矩阵记录访问过的元素值，从而避免同一个单元格多次统计；还有就是由于解的区域是三角形，可以仅考虑搜索右下方向来进行矩阵搜索。【很有意思的点，如果直接四个方向访问的话，会出现栈溢出的情况】

4.3 数据类型功能函数总结

//数组相关操作
int[] array_name=new int[]{初始的元素值};//数组定义方式1
int[] array_name=new int[len];//数组定义方式2
//矩阵相关操作
int[][] array_name=new int[line_len][row_len];//矩阵定义
//队列相关操作
LinkedList<> queue_name=new LinkedList<>();//队列结构用linkedlist实现
queue_name.add();//添加元素
queue_name.poll();//弹出元素
queue_name.size();//获得队列大小

4.4 java代码

class Solution {int m,n,k;int[][] visited;public int movingCount(int m, int n, int k) {int re=1;visited=new int[m][n];re=dfs(m,n,k,0,0);return re;}public int dfs(int m, int n, int k,int i,int j) {if(i>=m||j>=n||i<0||j<0||i%10+i/10+j%10+j/10>k||visited[i][j]==1){return 0;}else{visited[i][j]=1;int re=1;re+=dfs(m,n,k,i+1,j)+dfs(m,n,k,i,j+1);return re;}}
}

4.5 另解

搜索回溯类的问题另外一种解法思路是广度优先遍历，深度优先遍历DFS需要借助栈结构，可递归实现，对应的，广度优先遍历需要借助队列结构。

class Solution {int m,n,k;int[][] visited;LinkedList queue=new LinkedList();//队列结构public int movingCount(int m, int n, int k) {int re=0;visited=new int[m][n];//广度优先遍历queue.add(new int[]{0,0});//初始的i，jwhile(queue.size()!=0){int[] temp=queue.poll();int i=temp[0],j=temp[1];if(i=0 && j>=0 && (i/10+i%10+j/10+j%10)<=k && visited[i][j]!=1){re++;//统计到达的格子queue.add(new int[]{i+1,j});queue.add(new int[]{i,j+1});visited[i][j]=1;}}return re;}
}

又是只完成一半任务的一周（衰