1、动态规划

动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们先来讲下做动态规划题很重要的三个步骤：

1. 第一步骤：定义数组元素的含义，上面说了，我们会用一个数组，来保存历史数组，假设用一维数组 dp[] 吧。这个时候有一个非常非常重要的点，就是规定你这个数组元素的含义，例如你的 dp[i] 是代表什么意思？
2. 第二步骤：状态转移方程，找出数组元素之间的关系式，我觉得动态规划，还是有一点类似于我们高中学习时的归纳法的，当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2]……dp[1]，来推出 dp[n] 的，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。而这一步，也是最难的一步。
3. 第三步骤：找出初始值。学过数学归纳法的都知道，虽然我们知道了数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，我们可以通过 dp[n-1] 和 dp[n-2] 来计算 dp[n]，但是，我们得知道初始值啊，例如一直推下去的话，会由 dp[3] = dp[2] + dp[1]。而 dp[2] 和 dp[1] 是不能再分解的了，所以我们必须要能够直接获得 dp[2] 和 dp[1] 的值，而这，就是所谓的初始值。

有了初始值，并且有了数组元素之间的关系式，那么我们就可以得到 dp[n] 的值了，而 dp[n] 的含义是由你来定义的，你想求什么，就定义它是什么，这样，这道题也就解出来了。

- 案例一

class Solution {
    //解题思路：动态规划
    //状态转移方程：比如，如果想指导amout为11时的最少硬币数，如果你凑出amout=10的最少硬币数，你只需要加一就可以得到amount=11的最少硬币数。
    public int coinChange(int[] coins, int amount) {
        //自底而上求
        int max=amount+1;
        //dp[n]:当amout为n时，凑成的硬币最少个数
        int[] dp=new int[amount+1];
        //把数组中的元素都变为max
        Arrays.fill(dp,max);
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                //判断条件
                if(coins[j]<=i){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}

2、回溯法

解决⼀个回溯问题，实际上就是⼀个决策树的遍历过程。你只需要思考 3 个问题：

• 路径：也就是已经做出的选择。
• 选择列表：也就是你当前可以做的选择。
• 结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法的框架：

• 案例一

class Solution {
    private List<List<Integer>> list1=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0){
            return list1;
        }
        int sum=0;
        int index=0;
        Arrays.sort(candidates);
        List<Integer> list=new LinkedList<>();
        backtrace(candidates,target,list,sum,index);
        return list1;
    }
    public void backtrace(int[] arr,int target,List<Integer> list,int sum,int index){
        //结束条件
        if(sum==target){
            list1.add(new LinkedList(list));
            return;
        }
        for(int i=index;i<arr.length;i++){
            if(target-sum<arr[i]){
                break;
            }
            list.add(arr[i]);
            sum=sum+arr[i];
            backtrace(arr,target,list,sum,i);
            list.remove(list.size()-1);
            sum=sum-arr[i];
        }

    }
}

• 案例二
  

class Solution {
    private List<List<Integer>> list=new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length<1){
            return list;
        }
        int[] flag=new int[nums.length];
        backtrace(nums,flag,nums.length,new LinkedList<>());
        return list;
    }
    private void backtrace(int[] num,int[] flag,int len,List<Integer> list2){
        if(list2.size()==len){
            list.add(new ArrayList<>(list2));
            return;
        }
        for(int i=0;i<num.length;i++){
            if(flag[i]==1){
                continue;
            }
            flag[i]=1;
            list2.add(num[i]);
            backtrace(num,flag,len,list2);
            flag[i]=0;
            list2.remove(list2.size()-1);
        }
    }
}

• 案例三
  

class Solution {
    // 每步要么增加一个左括号，要么增加一个右括号，是一个二叉的选择，所以暴搜很容易写出来，就是dfs(left - 1, right, curStr + "("); dfs(left, right - 1, curStr + ")"); 
    //但是并不是每个分支都是符合要求的（正确的括号匹配），比如如果right使用的比left多的话就已经不是正确括号了，没必须继续dfs这个分支了，所以加上if来剪枝哈～
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, n, "");
        return res;
    }
    private void dfs(int left, int right, String curStr) {
        if (left == 0 && right == 0) { // 左右括号都不剩余了，递归终止
            res.add(curStr);
            return;
        }

        if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
            dfs(left - 1, right, curStr + "(");
        }
        if (right > left) { // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
            dfs(left, right - 1, curStr + ")");
        }
}
}

3、深度优先遍历算法

class Solution {
    //深度优先遍历
    private int[][] nums=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    public int numIslands(char[][] grid) {
        if(grid.length==0){
            return 0;
        }
        int row=grid.length;
        int col=grid[0].length;
        //岛屿的个数
        int count=0;
        //记录被遍历过的位置
        boolean[][] arr=new boolean[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]=='1'&&arr[i][j]==false){
                    count++;
                    dfs(arr,grid,i,j,row,col);
                }
            }
        }
        return count;
    }
    public void dfs(boolean[][] arr,char[][] grid,int x,int y,int row,int col){
        arr[x][y]=true;
        for(int[] num:nums){
            int curRow=num[0]+x;
            int curCol=num[1]+y;
            if(judgeRange(curRow,curCol,row,col)&&arr[curRow][curCol]==false&&grid[curRow][curCol]=='1'){
                dfs(arr,grid,curRow,curCol,row,col);
            }
        }
    }
    public boolean judgeRange(int x,int y,int row,int col){
        if(x>=0&&x<row&&y>=0&&y<col){
            return true;
        }
        return false;
    }
}

4、广度优先遍历算法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //解题思路：广度优先遍历
    //广度优先遍历是按层层推进的方式，遍历每一层的节点;题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适
    //广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new LinkedList<>();
        if(root==null){
            return list;
        }
        LinkedList<TreeNode> deque=new LinkedList<>();
        //将根节点放入队列中，然后不断遍历队列
        deque.add(root);
        while(deque.size()>0){
            //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
            int len=deque.size();
            List<Integer> list1=new LinkedList<>();
            //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
            //如果节点的左/右子树不为空，也放入队列中
            for(int i=0;i<len;i++){
                TreeNode node=deque.poll();
                list1.add(node.val);
                if(node.left!=null){
                   deque.add(node.left);
                }
                if(node.right!=null){
                deque.add(node.right);
                }
            }
            //将临时list加入最终返回结果中
            list.add(list1);
        }
        return list;

    }
}

5、滑动窗口算法

class Solution {
    //滑动窗口，left=right=0
    //向右移动窗口，直到[left，right]包含t，然后不断增大left，直到[left，right]不包含t
    //不断重复上一步骤，直到遍历结束
    public String minWindow(String s, String t) {
        //保存t中的每个字符，以及字符出现的次数
        int[] arr1=new int[128];
        //保存s中的目标字符，以及出现的次数
        int[] arr2=new int[128];
        int left=0;
        int right=0;
        for(int i=0;i<t.length();i++){
            arr1[t.charAt(i)]++;
        }
        int count=0;
        int start=0;
        int min=s.length()+1;
        while(right<s.length()){
            //如果当前字符不是目标字符，则直接进入下一轮循环
            if(arr1[s.charAt(right)]==0){
                right++;
                continue;
            }
            if(arr2[s.charAt(right)]<arr1[s.charAt(right)]){               
                count++;
            }
            arr2[s.charAt(right)]++;
            right++;
            //当窗口内包含t的全部字符，则开始从左侧缩小窗口
            while(count==t.length()){
                //若窗口符合条件，且长度比较小，则对min重新赋值
                if(right-left<min){
                    start=left;
                    min=right-left;
                }
                //起点字符不是目标字符
                if(arr1[s.charAt(left)]==0){
                    left++;
                    continue;
                }
                //起点字符是目标字符，且arr1[s.charAt(left)]==arr2[s.charAt(left)]
                if(arr1[s.charAt(left)]==arr2[s.charAt(left)]){
                    count--;                   
                }
                arr2[s.charAt(left)]--;
                left++;         
            }

        }
        if(min==s.length()+1){
            return "";
        }else{
            return s.substring(start,start+min);
        }

    }
}

class Solution {
    //滑动窗口，left=right=0
    //向右移动窗口，直到[left，right]包含t，然后不断增大left，直到[left，right]不包含t
    //不断重复上一步骤，直到遍历结束
    public boolean checkInclusion(String s1, String s2) {
        //窗口的起点
        int left=0;
        //窗口的额终点
        int right=0;
        //目标字符在窗口内出现的次数
        int count=0;
        //因为字符一共只有127个
        int[] arr1=new int[128];
        int[] arr2=new int[128];
        //把目标字符串中的我字符全部添加到数组arr1中
        for(int i=0;i<s1.length();i++){
            arr1[s1.charAt(i)]++;
        }
        while(right<s2.length()){
            //若当前字符不是目标字符，则扩大窗口，进入下一轮循环
            if(arr1[s2.charAt(right)]==0){
                right++;
                continue;
            }
            //若当前字符是目标字符，且该字符的出现次数小于s1中目标字符出现的次数
            if(arr2[s2.charAt(right)]<arr1[s2.charAt(right)]){
                count++;
            }
            arr2[s2.charAt(right)]++;
            right++;
            //若s1的全部字符全部出现在窗口内
            while(count==s1.length()){
                //若窗口的长度等于s1的长度，且窗口内包含全部的s1字符
                if(right-left==s1.length()){
                    return true;
                }
                //当前字符不是目标字符
                if(arr1[s2.charAt(left)]==0){
                    left++;
                    continue;
                }
                //若当前字符是目标字符
                if(arr1[s2.charAt(left)]==arr2[s2.charAt(left)]){
                    count--;
                }
                arr2[s2.charAt(left)]--;
                left++;
                
            }
        }
        return false;

    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            /**
            1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
             此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

            2、如果当前字符 ch 包含在 map中，此时有2类情况：
             1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
             那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
             2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
             而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，              map.get(a)=0；
             随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际              上，left此时
             应该不变，left始终为2，子段变成 ba才对。

             为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
             另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
             因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */ 
            if(map.containsKey(s.charAt(i))){
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
        
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        //窗口的左右索引
        int left=0;
        int right=0;
        //窗口内目标字符出现的次数
        int count=0;
        //存储结果
        List<Integer> list=new LinkedList<>();
        //字符最多为127个
        int[] arr1=new int[128];
        int[] arr2=new int[128];
        //把目标字符串的字符保存到数组中
        for(int i=0;i<p.length();i++){
            arr1[p.charAt(i)]++;
        }
        while(right<s.length()){
            //当前字符不是目标字符
            if(arr1[s.charAt(right)]==0){
                right++;
                continue;
            }
            //当前字符是目标字符
            if(arr2[s.charAt(right)]<arr1[s.charAt(right)]){
                count++;
            }
            arr2[s.charAt(right)]++;
            right++;
            while(count==p.length()){
                if(right-left==p.length()){
                        list.add(left);                   
                }
                if(arr1[s.charAt(left)]==0){
                    left++;
                    continue;
                }
                if(arr1[s.charAt(left)]==arr2[s.charAt(left)]){
                    count--;
                }
                arr2[s.charAt(left)]--;
                left++;
                
            }
        }
        return list;

    }
}

6、二分法

class Solution {
    //二分法，先判断两个区间哪个是有序的区间，然后根据两个区间的性质判断target可能出现在那个区间
    public int search(int[] nums, int target) {
        if(nums.length==0){
            return -1;
        }else if(nums.length==1){
            if(nums[0]==target){
                return 0;
            }else{
                return -1;
            }
        }
        int l=0;
        int r=nums.length-1;
        while(l<=r){
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;

    }
}

1、为什么while循环的条件是<=，而不是<?
答：因为初始化 right 的赋值是 nums.length - 1 ，即最后⼀个元素的索引，⽽不是 nums.length 。

这⼆者可能出现在不同功能的⼆分查找中，区别是：前者相当于两端都闭区间 [left, right] ，后者相当于左闭右开区间 [left, right) ，因为索引⼤⼩为 nums.length 是越界的。

我们这个算法中使⽤的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进⾏搜索的区间。

7、双指针技巧汇总

我把双指针技巧再分为两类，⼀类是「快慢指针」，⼀类是「左右指针」。前者解决主要解决链表中的问题，⽐如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，⽐如⼆分查找。

7.1、快慢指针的用法

7.1.1判断链表中是否有环

经典解法就是⽤两个指针，⼀个跑得快，⼀个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针⼀圈，和慢指针相遇，说明链表含有环。

7.1.2已知链表中含有环，返回这个环的起始位置

ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        slow = head;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

可以看到，当快慢指针相遇时，让其中任⼀个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。这是为什么呢？

第⼀次相遇时，假设慢指针 slow ⾛了 k 步，那么快指针 fast ⼀定⾛了 2k步，也就是说⽐ slow 多⾛了 k 步（也就是环的⻓度）。

设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k -m，也就是说如果从 head 前进 k - m 步就能到达环起点。巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。

所以，只要我们把快慢指针中的任⼀个重新指向 head，然后两个指针同速前进，k - m 步后就会相遇，相遇之处就是环的起点了。

7.1.3寻找链表的中点

类似上⾯的思路，我们还可以让快指针⼀次前进两步，慢指针⼀次前进⼀步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// slow 就在中间位置
return slow;

当链表的⻓度是奇数时，slow 恰巧停在中点位置；如果⻓度是偶数，slow最终的位置是中间偏右。

7.1.4链表的归并排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 参考：Sort List——经典（链表中的归并排序） https://www.cnblogs.com/qiaozhoulin/p/4585401.html
     * 
     * 归并排序法：在动手之前一直觉得空间复杂度为常量不太可能，因为原来使用归并时，都是 O(N)的，
     * 需要复制出相等的空间来进行赋值归并。对于链表，实际上是可以实现常数空间占用的（链表的归并
     * 排序不需要额外的空间）。利用归并的思想，递归地将当前链表分为两段，然后merge，分两段的方
     * 法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，知道快的走到了末尾，然后
     * 慢的所在位置就是中间位置，这样就分成了两段。merge时，把两段头部节点值比较，用一个 p 指向
     * 较小的，且记录第一个节点，然后 两段的头一步一步向后走，p也一直向后走，总是指向较小节点，
     * 直至其中一个头为NULL，处理剩下的元素。最后返回记录的头即可。
     * 
     * 主要考察3个知识点，
     * 知识点1：归并排序的整体思想
     * 知识点2：找到一个链表的中间节点的方法
     * 知识点3：合并两个已排好序的链表为一个新的有序链表
     */
    public ListNode sortList(ListNode head) {
        return head==null?null:megerSort(head);
    }
    public ListNode megerSort(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        //慢指针的位置
        ListNode low=head;
        //快指针的位置
        ListNode fast=head;
        //记录当前慢指针的位置
        ListNode pre=null;
        while(fast!=null&&fast.next!=null){
            pre=low;
            low=low.next;
            fast=fast.next.next;
        }
        //断开链表
        pre.next=null;
        ListNode l=megerSort(head);
        ListNode r=megerSort(low);
        return  meger(l,r);
    }
    public ListNode meger(ListNode l,ListNode r){
        ListNode root=new ListNode(0);
        ListNode curRoot=root;
        while(l!=null&&r!=null){
            if(l.val<r.val){
                curRoot.next=l;
                curRoot=curRoot.next;
                l=l.next;
            }else{
                curRoot.next=r;
                curRoot=curRoot.next;
                r=r.next;
            }
        }
        while(l!=null){
            curRoot.next=l;
            curRoot=curRoot.next;
            l=l.next;
        }
        while(r!=null){
            curRoot.next=r;
            curRoot=curRoot.next;
            r=r.next;
        }
        return root.next;
    }
}

7.1.5寻找链表的倒数第k个元素

我们的思路还是使⽤快慢指针，让快指针先⾛ k 步，然后快慢指针开始同速前进。这样当快指针⾛到链表末尾 null 时，慢指针所在的位置就是倒数第 k个链表节点（为了简化，假设 k 不会超过链表⻓度）：

ListNode slow, fast;
slow = fast = head;
while (k-- > 0)
   fast = fast.next;
while (fast != null) {
   slow = slow.next;
   fast = fast.next;
}
return slow;

7.1、左右指针的用法

左右指针在数组中实际是指两个索引值，⼀般初始化为 left = 0, right =nums.length - 1 。

7.2.1二分查找

int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (right + left) / 2;
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }

7.2.2两数之和

int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
            // 题⽬要求的索引是从 1 开始的
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++; // 让 sum ⼤⼀点
            } else if (sum > target) {
                right--; // 让 sum ⼩⼀点
            }
        }
        return new int[]{-1, -1};
    }

需要注意的是：如果是求中点的值，在int left = 0, right = nums.length - 1;的情况下，left<=right，但在这种情况况下是left<right。

7.2.3反转数组

void reverse(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
        // swap(nums[left], nums[right])
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++; right--;
        }
    }

8、买股票问题通用解法

动态规划求解：

• 定义数组含义：dp[i][k][0 or 1]，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（ 1 表示持有股票，0 表示没有持有股票）。
• 状态转移方程：

根据这个图，我们来写一下状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,             选择 sell      )

解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )

解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

这个解释应该很清楚了，如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的(只能选择一种方式减1，即买的时候减1或者卖的时候减1)。

在，我们已经完成了动态规划中最困难的一步：状态转移方程。如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。不过还差最后一点点，就是定义 base case，即最简单的情况。

dp[-1][k][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
dp[-1][k][1] = -infinity
解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。
dp[i][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

把上面的状态转移方程总结一下：

base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

8.1、买股票的最佳时机

解题思路：因为只交易一次k=1,所以

dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) 
            = max(dp[i-1][1][1], -prices[i])
解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。

现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])

当i=0时，dp[0][0]=max(0,负无穷)=0；
当i=0时，dp[0][1]=max(负无穷,-prices[i])=-prices[i]；

所以这一题的代码为：

class Solution {
    /**
    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
    **/
    public int maxProfit(int[] prices) {
        if(prices.length<2){
            return 0;
        }
        int[][] dp=new int[prices.length][2];
        for(int i=0;i<prices.length;i++){
            if(i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
            }else{
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
                dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
            }
        }
        return dp[prices.length-1][0];
    }
}

8.2、买股票的最佳时机`

class Solution {
    //dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]);
    //dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][1]-prices[i]);
    //因为这里k是无穷大所以状态转移方程为：
    //dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
    //dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
    public int maxProfit(int[] prices) {
        if(prices.length<2){
            return 0;
        }
        int[][] dp=new int[prices.length][2];
        for(int i=0;i<prices.length;i++){
            if(i==0){
                //当i=0时，dp[0][0]=max{dp[-1][0],dp[-1][1]+prices[i]}=max{0,负无穷}=0
                //dp[0][1]=max{dp[-1][1],dp[-1][0]-prices[i]}=max{负无穷,-prices[i]}=-prices[i]
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            
        }
        return dp[prices.length-1][0];
    }
}

8.3、买股票的最佳时机(三)

class Solution {
    //dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    //dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
    //当k=2时，就不能进行优化把k去掉
    public int maxProfit(int[] prices) {
        if(prices.length<2){
            return 0;
        }
        int[][][] dp=new int[prices.length][3][2];
        for(int i=0;i<prices.length;i++){
            for(int k=1;k<=2;k++){
                if(i==0){
                    dp[i][k][0]=0;
                    dp[i][k][1]=-prices[0];
                }else{
                    dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                    dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
                }
            }
        }
        return dp[prices.length-1][2][0];
    }
}

8.4、买股票的最佳时机(四)

分析：有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别。但是出现了一个超内存的错误，原来是传入的 k 值会非常大，dp 数组太大了。现在想想，交易次数 k 最多有多大呢？

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。

class Solution {
    public int maxProfit(int k, int[] prices) {
        //这里k不是无穷大，所以状态方程为：
        //dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
        //dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
        if(prices.length<2){
            return 0;
        }
        if(k>prices.length/2){
            return maxProfit_nonek(prices);
        }
        int[][][] dp=new int[prices.length][k+1][2];
        for(int i=0;i<prices.length;i++){
            for(int j=1;j<=k;j++){
                if(i==0){
                    dp[i][j][0]=0;
                    dp[i][j][1]=-prices[0];
                }else{
                    dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                    dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
                }
            }
        }
        return dp[prices.length-1][k][0];
    }
    private int maxProfit_nonek(int[] price){
        //这里相当于k无穷大，所以状态转移方程为：
        //dp[i][0]=max{dp[i-1][0],dp[i-1][1]+price[i]}
        //dp[i][1]=max{dp[i-1][1],dp[i-1][0]-price[i]}
        int[][] dp=new int[price.length][2];
        for(int i=0;i<price.length;i++){
            if(i==0){
                dp[i][0]=0;
                dp[i][1]=-price[0];
            }else{
                dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i]);
                dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-price[i]);
            }
        }
        return dp[price.length-1][0];
    }
}

8.5、最佳买卖股票实际含冷冻期

每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。

class Solution {
    //dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
    //dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
    //每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：
    //dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
    //dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
    public int maxProfit(int[] prices) {
        if(prices.length<2){
            return 0;
        }
        int[][] dp=new int[prices.length][2];
        for(int i=0;i<prices.length;i++){
            if(i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
            }else if(i==1){
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1]=Math.max(dp[0][1],-prices[i]);
            }else{
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
            }
        }
        return dp[prices.length-1][0];
    }
}

8.6、最佳买卖股票实际含手续费

j为无穷大，每笔交易需要付手续费，所以状态方程为：

dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]-fee);

class Solution {
    //dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
    //dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
    //j为无穷大，每笔交易需要付手续费，所以状态方程为：
    //dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
    //dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]-fee);
    public int maxProfit(int[] prices, int fee) {
        if(prices.length<2){
            return 0;
        }
        int[][] dp=new int[prices.length][2];
        for(int i=0;i<prices.length;i++){
            if(i==0){
                dp[i][0]=0;
                dp[i][1]=-prices[i]-fee;
            }else{
                dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]-fee);
            }
        }
        return dp[prices.length-1][0];
    }
}

9、打家劫舍(三)

class Solution {
    //首先想到的是用递归解决，但是为了避免重复的计算，这里使用HashMap保存结果
    private HashMap<TreeNode,Integer> map=new HashMap<>();
    public int rob(TreeNode root) {
        //结束条件
        if(root==null){
            return 0;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        //接下来要分情况讨论，当前节点root是否偷窃，max=Math.max(偷窃root节点，不偷窃root节点)
        //若偷窃root节点
        int tem1=root.val+(root.left==null?0:rob(root.left.left)+rob(root.left.right))+(root.right==null?0:rob(root.right.left)+rob(root.right.right));
        //若不偷窃root节点
        int tem2=rob(root.left)+rob(root.right);
        //保存结果，避免重复的计算
        map.put(root,Math.max(tem1,tem2));
        return Math.max(tem1,tem2);
    }
}

10、多数之和

思路：先排序，在使用双指针。

10.1、两数之和

思路：题目要求返回，满足条件的索引，所以不能使用先排序，后双指针的方法。这里采用一遍哈希表。

class Solution {
    //一遍哈希表
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

10.2、三数之和

核心思路：先排序，后双指针。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list1=new ArrayList<>();
        if(nums.length<3){
            return list1;
        }
        //对数组进行排序
        Arrays.sort(nums);
        //双指针法，首先遍历整个数组
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                //若大于0，则后面不可能出现和等于0的数
                break;
            }
            //若元素重复，则直接进入下一轮循环
            if(i-1>=0&&nums[i]==nums[i-1]){
                continue;
            }
            //第一个指针的位置
            int left=i+1;
            //第二个指针的位置
            int right=nums.length-1;
            //双指针法的循环条件
            while(left<right){
                //若三个数之和大于0，右指针左移
                if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }else if(nums[i]+nums[left]+nums[right]<0){
                    //若三个数之和小于0，左指针右移
                    left++;
                }else{
                    //若三数之和等于0，直接添加
                    List<Integer> list=new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    list1.add(list);
                    int tem1=nums[right];
                    int tem2=nums[left];
                    right--;
                    left++;
                    //若指针在移动过程中出现相同的元素，则直接跳过，直到出现下一个不相等的元素
                    while(right>=0&&nums[right]==tem1){
                        right--;
                    }
                    while(left<nums.length&&nums[left]==tem2){
                        left++;
                    }
                    
                }
            }
            
        }
        return list1;

    }
    

}

10.3、四数之和

class Solution {
    //思路：和三数之和解题方法一样
    //利用两个for循环，固定四个元素中的最小的两个元素a和b，之后采用双指针法，left=a+1,right=len-1
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list=new LinkedList<>();
        if(nums.length<4){
            return list;
        }
        //排序
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
            //排除相等的元素
            if(i-1>=0&&nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.length-2;j++){
                //排除相等的元素
                if(j-1>i&&nums[j]==nums[j-1]){
                continue;
                }
                int tem=target-nums[i]-nums[j];
                int left=j+1;
                int right=nums.length-1;
                while(left<right){
                    if(nums[left]+nums[right]==tem){
                        List<Integer> list1=new LinkedList<>();
                        list1.add(nums[i]);
                        list1.add(nums[j]);
                        list1.add(nums[left]);
                        list1.add(nums[right]);
                        list.add(list1);
                        int curleft=nums[left];
                        int curright=nums[right];
                        left++;
                        right--;
                        //取出相同的元素
                        while(left<nums.length&&nums[left]==curleft){
                            left++;
                        }
                        while(right>=0&&nums[right]==curright){
                            right--;
                        }
                    }else if(nums[left]+nums[right]>tem){
                        right--;
                    }else{
                        left++;
                    }
                }
            }

        }
        return list;
    }
}