一、回溯

回溯是一种搜索方式，基于递归。
回溯的本质是穷举，穷举所有可能性，选出我们想要的效果。
回溯可以解决的问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合。
  • 切割问题：一个字符串按一定规则能切割出多少种可能。
  • 子集问题：一个N个数的集合有多少种符合条件的子集。
  • 排列问题：N个数按一定规则全排列，有多少种排列可能。
  • 棋盘问题：N皇后，解数独。

如何理解回溯法？
所有回溯法解决的问题都可以抽象为树形结构，回溯法解决的都是集合中递归查找子集，集合的大小构成了树的深度。
1）确定函数的返回值以及参数
回溯的返回值一般是void，但是参数不太容易确定，一般先写一遍逻辑，发现缺什么参数填什么参数。
2）回溯的中止条件
对应树形结构就是遇到了叶子节点。
回溯的遍历过程的伪代码如下：
void backtracking(参数){
if(中止条件){
存放结果；
}
for(选择; 本层集合中元素){
处理节点；
backtracking(路径，选择列表)；
回溯，撤销处理结果;
}
}
回溯的for循环就是横向遍历，递归是纵向遍历，回溯就是不断调整结果集!

1.组合

题目链接：https://leetcode-cn.com/problems/combinations/
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
思路：求组合，经典的回溯算法，可以把组合过程看成一颗树
算法专题 - 图1

  1.     public void backTacking1(int n,int k,int start,List<Integer> subList,List<List<Integer>> result){
  2.         if(subList.size() == k){
  3.             List<Integer> newList = new ArrayList<Integer>();
  4.             for(int t : subList){
  5.                 newList.add(t);
  6.             }
  7.             result.add(newList);
  8.             return;
  9.         }
  10.         for(int i = start; i <= n; ++i) {
  11.             subList.add(i);
  12.             backTacking1(n, k, i + 1, subList, result);
  13.             subList.remove(subList.size() - 1);
  14.         }
  15.     }

总结：回溯的基本模板就是这样。在做题的过程中遇到问题是始终输出为空集合，后来排查原因是因为添加的集合一直都是那个subList，无论添加多少个，引用指向的都是subList，随着subList最后归为空，result集合里面的元素都为空了。所以最后每次添加到subList集合中元素到result集合中的时候都要新建一个list来将subList中的元素拷贝进去在添加到result中。

2.组合总和

链接：https://leetcode-cn.com/problems/combination-sum-iii/
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。

示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
思路：通常的回溯算法，需要确定的中止条件为找到了三个值以及三个值的和已经为n才能结束。
为了剪枝，有些没必要的回溯就不要存在了，比如第一个数为2，后面两个数的值就限制在min(n-2,9)，如果n=5，就没必要再选大于3的值来递归了。

  1.     public List<List<Integer>> combinationSum3(int k, int n) {
  2.         List<Integer> subList = new ArrayList<>();
  3.         List<List<Integer>> result = new ArrayList<>();
  4.         backTacking2(1,k,n,subList,result);
  5.         return result;
  6.     }
  7.     public void backTacking2(int startIndex,int k,int ans,List<Integer> subList,List<List<Integer>> result){
  8.         if(k == subList.size() && ans == 0){
  9.             List<Integer> newList = new ArrayList<Integer>();
  10.             for(int t : subList){
  11.                 newList.add(t);
  12.             }
  13.             result.add(newList);
  14.             return;
  15.         }
  16.         for(int i = startIndex; i < Math.min(ans+1,10); ++i){
  17.             subList.add(i);
  18.             backTacking2(i+1,k,ans-i,subList,result);
  19.             subList.remove(subList.size()-1);
  20.         }
  21.     }

总结：这种有求和之类的题可以边遍历边用和减去他，最后看差值是不是等于0。

3.组合总和2

题目链接：https://leetcode-cn.com/problems/combination-sum/
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]
示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
思路：三步走，1.确定终止条件，这里的中止条件是找到和为target的。2.确定函数参数，一个返回结果的集合；一个存储每次循环结束的数据的集合；target-每次添加的值，这样终止条件就判断是否为0了；还有一个index，为了去重的，后面说。

  1.     public List<List<Integer>> combinationSum(int[] candidates, int target){
  2.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  3.         List<Integer> list = new ArrayList<>();
  4.         backTracking4(result,list,0,candidates,target);
  5.         return result;
  6.     }
  7.     public void backTracking4(List<List<Integer>> result,List<Integer> list,int index,int[] candidates,int ans){
  8.         if(ans < 0){
  9.             return;
  10.         }
  11.         if(ans == 0){
  12.             List<Integer> newList = new ArrayList<Integer>();
  13.             for(Integer t : list){
  14.                 newList.add(t);
  15.             }
  16.             result.add(newList);
  17.             return;
  18.         }
  19.         for(int i = index; i < candidates.length; ++i){
  20.             list.add(candidates[i]);
  21.             backTracking4(result,list,i,candidates,ans-candidates[i]);
  22.             list.remove(list.size()-1);
  23.         }
  24.     }

遇到困难：做完第一遍感觉良好，运行完傻眼了，结果有重复的组合，比如[3,5],[5,3]想来想去这是程序的问题，这要去重啊，参考了下前面去重的方法，下图
68747470733a2f2f696d672d626c6f672e6373646e696d672e636e2f32303230313232333137303733303336372e706e67.png
这还需要一个index指针，让到第二元素的时候不让遍历第一个元素。
总结：上程序中传入的就是index，表示当前元素可以重复利用，像上一个程序，元素不可重复就传入的是index+1。天呀，我发现用new ArrayList(list);可以新建一个集合，把原来集合元素拷贝到新集合中。

4.切割字符串

题目链接：https://leetcode-cn.com/problems/palindrome-partitioning/
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,”b”], [“a”,”a”,”b”] ]
思路：涉及到两个关键问题：1）切割方式，2）判断是否为回文数。
算法专题 - 图3
切割问题用这个属性图来解决。
还是那句话，for循环横向遍历，递归纵向遍历。
终止条件就是切割线大于等于字符串长度，参数需要切割线位置

  1.     public void backTracking5(List<List<String>> result, List<String> list, String str,int index){
  2.         if(index >= str.length()){
  3.             result.add(new ArrayList<String>(list));
  4.             return;
  5.         }
  6.         for(int i = index; i < str.length(); ++i) {
  7.             if(isPalin(str.substring(index,i+1))){
  8.                 list.add(str.substring(index,i+1));
  9.             }else{
  10.                 continue;
  11.             }
  12.             backTracking5(result, list, str, i+1);
  13.             list.remove(list.size() - 1);
  14.         }
  15.     }
  16.     public boolean isPalin(String str){
  17.         if(str == null || "".equals(str)){
  18.             return false;
  19.         }
  20.         int startIndex = 0;
  21.         int lastIndex = str.length()-1;
  22.         while(startIndex <= lastIndex){
  23.             if(str.charAt(startIndex) != str.charAt(lastIndex)){
  24.                 return false;
  25.             }
  26.             startIndex++;
  27.             lastIndex--;
  28.         }
  29.         return true;
  30.     }

遇到问题：在做题过程中还是没有搞明白for循环横向遍历，递归纵向遍历这句话，现在更明白了一点。一开始我传入了一个参数是切割后的字符串，这导致我回溯的时候不知道怎么把字符串给还原。
总结：用一个指针来描述切割位置，for循环寻找下个切割位置，如果找到递归的时候就把下个切割位置传入作为下次递归的第一个切割位置，秒。

5.复原IP地址

题目地址：https://leetcode-cn.com/problems/restore-ip-addresses/
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：”0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。
示例 1： 输入：s = “25525511135” 输出：[“255.255.11.135”,”255.255.111.35”]
示例 2： 输入：s = “0000” 输出：[“0.0.0.0”]
示例 3： 输入：s = “1111” 输出：[“1.1.1.1”]
示例 4： 输入：s = “010010” 输出：[“0.10.0.10”,”0.100.1.0”]
示例 5： 输入：s = “101023” 输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]
提示： 0 <= s.length <= 3000 s 仅由数字组成
思路：本题和上一题有点类似，我的思路是先用数组装起来四个ip段的数据，最后转换为字符串放到结果数组中。本题还是切割，我用的是上一题的思路，判断每一段的数组是否有效，终止条件是index达到了字符串长度并且递归深度达到了4（也就是字段数）。

  1.     public List<String> restoreIpAddresses(String s) {
  2.         if(s.length() < 4){
  3.             return new ArrayList<>();
  4.         }
  5.         List<String> result = new ArrayList<>();
  6.         List<String> sb = new ArrayList<>();
  7.         backTracking6(result,s,0,sb,0);
  8.         return result;
  9.     }
  10.     public void backTracking6(List<String> list,String str,int index,List<String> sb,int deep){
  11.         if(index >= str.length() && deep == 4){
  12.             StringBuilder s1 = new StringBuilder();
  13.             for(int i = 0; i < sb.size()-1; ++i){
  14.                 s1.append(sb.get(i)+'.');
  15.             }
  16.             s1.append(sb.get(sb.size()-1));
  17.             list.add(s1.toString());
  18.             return;
  19.         }
  20.         for(int i = index; i < Math.min(index + 3,str.length()) && deep <= 4;++i){
  21.             String ip0 = str.substring(index,i+1);
  22.             if(Integer.parseInt(ip0) <= 255 && Integer.parseInt(ip0) >= 0 && isNormalDigit(ip0)){
  23.                 sb.add(ip0);
  24.             }else{
  25.                 continue;
  26.             }
  27.             backTracking6(list,str,i+1,sb,deep+1);
  28.             sb.remove(sb.size()-1);
  29.         }
  30.     }
  31.     public boolean isNormalDigit(String str){
  32.         int num = Integer.parseInt(str);
  33.         int count = 0; //计数
  34.         if(num == 0){
  35.             count = 1;
  36.         }else {
  37.             while (num >= 1) {
  38.                 num /= 10;
  39.                 count++;
  40.             }
  41.         }
  42.         if(count == str.length()){
  43.             return true;
  44.         }
  45.         return false;
  46.     }

遇到困难：这道题我傻逼了，判断一个字符串第一个数字是不是等于0就可以解决的问题我用数字的长度和字符串长度去比较。
还有可以不用去比较index是否大于字符串长度来确定终止条件，只需要判断深度就行了，只要每段数字是合法的，也不过说在for循环那个就确定好每段的长度，只要大于长度自然也不合法，也就不会继续递归。改后的代码

6.子集

题目地址：https://leetcode-cn.com/problems/subsets/
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
思路：这道题算是组合把，不过这道跟前面的不一样的地方是存放数据不止中止条件的时候存放，而是每次递归都存放。

  1.     public List<List<Integer>> subsets(int[] nums) {
  2.         List<List<Integer>> result = new ArrayList<>();
  3.         List<Integer> list = new ArrayList<>();
  4.         backTracking7(result,list,nums,0);
  5.         return result;
  6.     }
  7.     public void backTracking7(List<List<Integer>> result, List<Integer> list,int[] nums, int index ){
  8.         if(index > nums.length) {
  9.             return;
  10.         }
  11.         result.add(new ArrayList<Integer>(list));
  12.         for(int i = index; i < nums.length; ++i){
  13.             list.add(nums[i]);
  14.             backTracking7(result,list,nums,i+1);;
  15.             list.remove(list.size()-1);
  16.         }
  17.     }

总结：把问题想象成一棵树，以前是只收集叶子节点，现在收集的是每一个节点。

7.N皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

  • 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

思路：这题的每次递归结束的终止条件是递归深度达到了n，这点很好理解；这题的难点在于什么时候该存储，也就是判断这个点能否存储，主要从三个点去判断，该列前几行有无Q，该点的斜线在前几行是否有元素。

  1.     public List<List<String>> solveNQueens(int n) {
  2.         List<List<String>> result = new ArrayList<>();
  3.         char[][] queue = new char[n][n];
  4.         backTracking8(result,queue,n,0);
  5.         return result;
  6.     }
  7.     public void backTracking8(List<List<String>> result,char[][] queue,int n,int deep){
  8.         if(deep >= n){
  9.             result.add(array2list(queue));
  10.             return;
  11.         }
  12.         for(int i = 0; i < n; ++i){
  13.             if(isValid(queue,deep,i)){
  14.                 queue[deep][i] = 'Q';
  15.                 backTracking8(result,queue,n,deep+1);
  16.                 queue[deep][i] = '.';       //撤销放皇后
  17.             }
  18.         }
  19.     }
  20.     public boolean isValid(char[][] queue,int row,int col){
  21.         //检查行上有没有Q
  22.         for(int i = row-1; i >= 0; --i){
  23.             if(queue[i][col] == 'Q'){
  24.                 return false;
  25.             }
  26.         }
  27.         //检查左上斜线有没有Q
  28.         for(int i = row-1, j = col -1; i >=0 && j>= 0; i--,j--){
  29.             if(queue[i][j] == 'Q'){
  30.                 return false;
  31.             }
  32.         }
  33.         //检查右下斜线有没有Q
  34.         for(int i = row-1, j = col+1; i >=0 && j < queue[i].length; i--,j++){
  35.             if(queue[i][j] == 'Q'){
  36.                 return false;
  37.             }
  38.         }
  39.         return true;
  40.     }
  41.     public List<String> array2list(char[][] queue){
  42.         List<String> list = new ArrayList<>();
  43.         for(int i = 0; i < queue.length; ++i){
  44.             StringBuilder sb = new StringBuilder();
  45.             for(int j = 0; j < queue[i].length; ++j){
  46.                 if(queue[i][j] != 'Q'){
  47.                     queue[i][j] = '.';
  48.                 }
  49.                 sb.append(queue[i][j]);
  50.             }
  51.             list.add(sb.toString());
  52.         }
  53.         return list;
  54.     }

遇到困难：开始想用一个boolean的二维数组来放哪些点可以放，哪些点不能放，但是撤回操作的时候就懵了。开始还是在意存储结构的问题，这题中用数组直接存储，后面用一个函数转换一下就OK。开始想用一个list来放之前存放的位置，这样就很难找到一个规则来进行判断当前元素能否存储。
总结：要懂得灵活变通。

二、贪心算法

什么是贪心算法？
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
贪心算法没有固定的套路，唯一难点是如何通过局部最优推出全局最优，至于能不能通过局部最优推出整体最优最好的策略就是举反例，看有没有反例能推翻局部最优不能退出全局最优，如果有机不能推出。
贪心算法的一般步骤：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解

  • 将局部最优解堆叠成全局最优解

    1.分发饼干

    题目链接：https://leetcode-cn.com/problems/assign-cookies/
    假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
    对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
    示例 1: 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。
    示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.
    提示：

  • 1 <= g.length <= 3 * 10^4

  • 0 <= s.length <= 3 * 10^4
  • 1 <= g[i], s[j] <= 2^31 - 1

思路：大尺寸的饼干既可以满足胃口大的小孩，也能满足胃口小的小孩，那就优先满足胃口大的小孩。
这里的局部最优就是先满足胃口大的小孩。
先将数组排序，用大饼干满足先满足胃口大的。

  1.     public int findContentChildren(int[] g, int[] s) {
  2.         int count = 0;
  3.         Arrays.sort(g);
  4.         Arrays.sort(s);
  5.         int i = g.length - 1;
  6.         int j = s.length - 1;
  7.         while(i >= 0 && j >= 0){
  8.             if(s[j] >= g[i]){
  9.                 count++;
  10.                 j--;
  11.                 i--;
  12.             }else{
  13.                i--;
  14.             }
  15.         }
  16.         return count;
  17.     }

总结：贪心算法的全局最优我不知道怎么整，那我就想什么是局部最优，看满足局部最优能不能满足全局最优，这点还是需要多加练习。

2.最大子序和

题目地址：https://leetcode-cn.com/problems/maximum-subarray/
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：暴力法很简单，但是用贪心算法的话时间复杂度为O(n)
在相加过程中，如果遇到负数那么一定会将和的值变小，在加的过程中，如果总和为负数之后再加上后面的值一定会让总和变小，所以当总和为负的时候就应当舍弃当前序列，从下一个数开始累加。
局部最优：当连续和为负数的时候放弃，从下一个开始重新累加
全局最优：选取最大连续和。

  1.     public int maxSubArray(int[] nums){
  2.         int result = Integer.MIN_VALUE;
  3.         int sum = 0;
  4.         for(int i = 0; i < nums.length; ++i){
  5.             sum += nums[i];
  6.             if(sum > result){
  7.                 result = sum;
  8.             }
  9.             if(sum < 0){
  10.                 sum = 0;
  11.             }
  12.         }
  13.         return result;
  14.     }

总结：做到这里贪心算法的套路还是难以琢磨，甚至我都看不出这是不是用贪心算法，哎，再多做几道题熟悉熟悉吧。
3.求股票最大利润
题目链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

思路1：本题和上题类似，这里的局部最优是每次买卖的时机，假设当股票一跌我就买，然后从跌入点开始买入，遇到跌了再在跌的前一天卖。
思路2：计算每一天与前一天的利润，然后叠加正利润。
算法专题 - 图4
局部最优：收集每天的正利润；全局最优：求得最大利润。
思路1代码：

  1.     public int maxProfit(int[] prices) {
  2.         int result = 0;
  3.         int prePrice = prices[0];
  4.         for(int i = 1; i < prices.length; ++i){
  5.             if(prices[i] - prices[i-1] < 0){
  6.                 result += (prices[i-1] - prePrice);
  7.                 prePrice = prices[i];
  8.             }
  9.             if(i == prices.length-1 && prices[i] - prePrice > 0){
  10.                 result += (prices[i] - prePrice);
  11.             }
  12.         }
  13.         return result;
  14.     }

思路2代码：

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int sum = 0;
  4.         int profit = 0;
  5.         int buy = prices[0];
  6.         for (int i = 1; i < prices.length; i++) {
  7.             profit = prices[i] - buy;
  8.             if (profit > 0) {
  9.                 sum += profit;
  10.             }
  11.             buy = prices[i];
  12.         }
  13.         return sum;
  14.     }
  15. }

总结：开始有一点感觉了，就是贪局部的最优。

3.跳跃游戏

题目链接：https://leetcode-cn.com/problems/jump-game/
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
思路：不需要计算需要调几步，只需要看跳跃的覆盖范围有没有覆盖到最后一个元素。写一个for循环，循环的中止条件是小于覆盖范围，我们每走一步都要计算覆盖范围，保留最大的覆盖范围。
算法专题 - 图5
第一个只要在覆盖范围内的说明一定走得到，不管怎么走的。
局部最优，每次取最大跳跃步数；整体最优：得到整体最大覆盖范围，看能否到终点。

  1.     public boolean canJump(int[] nums) {
  2.         int cover = 0;
  3.         for(int i = 0; i <= cover; ++i){
  4.             cover = Math.max(cover,i+nums[i]);
  5.             if(cover >= nums.length-1){
  6.                 return true;
  7.             }
  8.         }
  9.         return false;
  10.     }

总结：跳跃不用想着一步一步跳，记录能够跳跃的最大范围，说明这范围内的每个点我都能跳。

4.跳跃游戏2

题目地址：https://leetcode-cn.com/problems/jump-game-ii/
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明: 假设你总是可以到达数组的最后一个位置。
思路：可以反向跳跃，找到能够到达最后一点的位置，贪心的寻找离能到达最后一点最远的那个位置，然后依次向前寻找。

  1. public int jump(int[] nums) {
  2.         if(nums.length <= 1){
  3.             return 0;
  4.         }
  5.         int position = nums.length - 1;
  6.         int step = 0;
  7.         while(position >= 0){
  8.             for(int i = 0; i < position; ++i){
  9.                 if(i+nums[i] >= position){
  10.                     step++;
  11.                     position = i;
  12.                     break;
  13.                 }
  14.             }
  15.         }
  16.         return step;
  17.     }

该思路的时间复杂度是O(n^2)，太复杂了。
思路2：正向贪心，从第一个位置开始寻找能够走到最远的一个位置，比如
2,3,1,2,4,2,3 ；
第一个是2，能够跳到3和1，然后看是第二个位置跳的远还是第三个位置跳的远，这里第2个位置跳得远，所以记下它的下标，到它这里的时候步数就加一。
算法专题 - 图6

  1.     public int jump2(int[] nums) {
  2.         int end = 0;
  3.         int maxStep = 0;
  4.         int step = 0;
  5.         for(int i = 0; i < nums.length-1; ++i){
  6.             maxStep = Math.max(maxStep,nums[i]+i);
  7.             if(i == end){
  8.                 end = maxStep;
  9.                 step++;
  10.             }
  11.         }
  12.         return step;
  13.     }

总结：代码中maxStep代表能够走到最远的位置，如果走到那说明这一步也走完了。开始找到下一步能走到最远的位置了。有点难，呜呜呜。

5.K次取反后最大化的数组和

题目地址：https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/
给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）
以这种方式修改数组后，返回数组可能的最大和。
示例 1： 输入：A = [4,2,3], K = 1 输出：5 解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2： 输入：A = [3,-1,0,2], K = 3 输出：6 解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3： 输入：A = [2,-3,-1,5,-4], K = 2 输出：13 解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：

  • 1 <= A.length <= 10000
  • 1 <= K <= 10000
  • -100 <= A[i] <= 100

思路：局部最优，让负数全部取反，
如果还剩余翻转次数，让最小的数一直翻转。

  1.     public int largestSumAfterKNegations(int[] nums, int k) {
  2.         int sum = 0;
  3.         Arrays.sort(nums);
  4.         int i = 0;
  5.         while(k > 0 && i < nums.length && nums[i] < 0){
  6.             nums[i] = -nums[i];
  7.             k--;
  8.             i++;
  9.         }
  10.         Arrays.sort(nums);
  11.         for(int j = 0; j < k; ++j){
  12.             nums[0] = -nums[0];
  13.         }
  14.         for(int t = 0; t < nums.length; ++t){
  15.             sum += nums[t];
  16.         }
  17.         return sum;
  18.     }

总结：总和最小就要尽可能的消灭最小的负数，如果消灭完负数了就让最小的数一直反转，最次结果也是减去这个最小的数。

6.加油站

题目链接：https://leetcode-cn.com/problems/gas-station/
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:

  • 如果题目有解，该答案即为唯一答案。
  • 输入数组均为非空数组，且长度相同。
  • 输入数组中的元素均为非负数。

示例 1: 输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2]
输出: 3 解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。 因此，3 可为起始索引。
示例 2: 输入: gas = [2,3,4] cost = [3,4,3]
输出: -1 解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。
思路：本题用贪心算法，看能不能游玩一圈，看总的油量是不是大于消耗量。
如果大于消耗量就贪心的找连续最大和的第一个索引位置，这题有点像前面的最大子序列和，最大子序列和的第一个位置就是我们要找的最优位置。这是我的思路。
算法专题 - 图7

  1.     public int canCompleteCircuit(int[] gas, int[] cost) {
  2.         int length  = gas.length;
  3.         int[] error = new int[length];
  4.         for(int i = 0; i < length; ++i){
  5.             error[i] = gas[i] - cost[i];
  6.         }
  7.         int resultIndex = -1;
  8.         int sum = 0;    //存储总剩余汽油
  9.         int sum1 = 0;
  10.         for(int i = 0; i < length; ++i){
  11.             sum += error[i];
  12.             sum1 += error[i];
  13.             if(sum1 < 0){
  14.                 sum1 = 0;
  15.                 resultIndex = i;
  16.             }
  17.         }
  18.         if(sum < 0){
  19.             return -1;
  20.         }
  21.         return resultIndex+1;
  22.     }

7.分发糖果

链接：https://leetcode-cn.com/problems/candy/
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2: 输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
思路：要先判断左边孩子大于右边孩子的情况，再判断右边孩子大于左边孩子的情况，其中左边孩子大于右边孩子要从前向后遍历，右边孩子大于左边孩子的情况要从后向前遍历。
想一下，如果判断左边孩子大于右边孩子情况从前遍历，这样是根据右边孩子的值来确定左边孩子的值，可是右边孩子的值都还没确定呢，怎么确定左边孩子的呢，相当于左边孩子的值都是根据右边孩子初始化的值来确定的。
换个说法，从左边的孩子大于右边孩子从前遍历，右边孩子：老子的值下一步才能确定，你怎么能拿我的值确定你的值呢。

  1.     public int candy(int[] ratings) {
  2.         int[] nums = new int[ratings.length];
  3.         for(int i = 0; i < nums.length; ++i){
  4.             nums[i] = 1;
  5.         }
  6.         for(int i = 1; i < ratings.length; ++i){
  7.             if(ratings[i] > ratings[i-1]){
  8.                 nums[i] = nums[i-1]+1;
  9.             }
  10.         }
  11.         for(int i = ratings.length - 2; i >= 0 ; --i){
  12.             if(ratings[i] > ratings[i+1]){
  13.                 nums[i] = Math.max(nums[i],nums[i+1]+1);
  14.             }
  15.         }
  16.         int sum = 0;
  17.         for(int i = 0;i < ratings.length; ++i){
  18.             sum += nums[i];
  19.         }
  20.         return sum;
  21.     }

遇到困难：一开始想直接比较两遍孩子的值来确定当前值，可是始终有一边的值没确定啊，所以先确定一遍。
总结：先从确定一边，再确定另一变！

三、动态规划

什么时候用动态规划：如果某一问题有很多重叠子问题，使用动态规划最有效。
动态规划中的每一个状态都是由上一个状态推导出来的，有别于贪心算法，贪心算法每次取一个局部最优组成全局最优，而动态规划每次拿的跟上一个状态有关。
动态规划步骤：
1.确定dp数组以及下标含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导数组
斐波那契数列的五步走：
1.确定dp数组以及下标含义
dp[i]：第i个数的斐波那契数值
2.确定递推公式
已经给出来了：dp[i] = dp[i-1]+dp[i-2]
3.确定初始化值
题目又给出来了dp[1]=1;dp[0]=0;
4.确定遍历顺序
从递推公式中看到dp[i] = dp[i-1]+dp[i-2],是从小的值推到大的值，那遍历顺序是从前向后的。
5.举例推导
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：0 1 1 2 3 5 8 13 21 34 55

1.爬楼梯

题目地址：https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

思路：
1.dp表的含义， dp[n]，到达第n个台阶所需要的步数
2.确定递推公式：
dp[n] = dp[n-1]+dp[n-2]；到达第n个台阶数为到达第n-1个台阶和第n-2个台阶之和
3.确定初始化值： dp[1]=1,dp[2]=2;
4.确定遍历顺序： 这个问题就是斐波那契数列问题，遍历顺序还是前向后。
5.举例推导
n=5， 1 2 3 5 8

  1.     public int climbStairs(int n) {
  2.         if(n <= 2){
  3.             return n;
  4.         }
  5.         int a = 1;
  6.         int b = 2;
  7.         int c = 0;
  8.         for(int i = 3; i <= n; ++i){
  9.             c = a + b;
  10.             a = b;
  11.             b = c;
  12.         }
  13.         return b;
  14.     }

总结：这种简单题的动态规划没啥问题，此题中用变量代替了dp表。

2.使用最小花费爬楼梯

题目链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs/
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。 示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：

  • cost 的长度范围是 [2, 1000]。
  • cost[i] 将会是一个整型数据，范围为 [0, 999] 。

思路：五步走
先确定dp[i]的含义：走到第i步所需要花费总体力
推导公式：dp[i] = min(d[i-1],dp[i-2])+cost[i]
确定初始值：dp[0]=cost[0];dp[1]=cost[1]
确定遍历顺序: 前向遍历
举例

  1.     public int minCostClimbingStairs(int[] cost) {
  2.         int[] dp = new int[cost.length];
  3.         dp[0] = cost[0];
  4.         dp[1] = cost[1];
  5.         for(int i = 2; i < cost.length; ++i){
  6.             dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];
  7.         }
  8.         return Math.min(dp[cost.length-1],dp[cost.length-2]);
  9.     }

总结：一开始我就是这么做的，后来举了个例子10,15，20算到dp[3]等于30就放弃了这个思路，但是后来看解析返回值是倒数两个值中最小的一个，顿时就悟了。

3.不同路径

题目链接：https://leetcode-cn.com/problems/unique-paths/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
算法专题 - 图8
输入：m = 3, n = 7 输出：28
示例 2： 输入：m = 2, n = 3 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 3： 输入：m = 7, n = 3 输出：28
示例 4： 输入：m = 3, n = 3 输出：6 提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10^9

思路：
1.dp[i][j]表示到达第i,j位置有多少种走法
2.推导公式，第i,j位置只能从上面和左边面走过来，所以dp[i][j] = dp[i-1][j]+dp[i][j-1];
3.初始化值dp[i][0]=1 和dp[0][j]=1，因为从dp[0][0]走过来只有一条路。
4.遍历顺序，看推导公式，都是从左向右走过来，从上向下走过来，所以i和j都从顺序遍历就好了。
5.举例

  1.     public int uniquePaths(int m, int n) {
  2.         int[][] dp = new int[m][n];
  3.         for(int i = 0; i < m; ++i){
  4.             dp[i][0] = 1;
  5.         }
  6.         for(int j = 0; j < n; ++j){
  7.             dp[0][j] = 1;
  8.         }
  9.         for(int i = 1; i < m; ++i){
  10.             for(int j = 1; j < n; ++j){
  11.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  12.             }
  13.         }
  14.         return dp[m-1][n-1];
  15.     }

总结：这个题可以用二叉树的遍历来做，找到叶子节点就是一条路径。但是时间复杂度是O(2^(m+n-1))。
但是用动态规划时间复杂度就是O(M*N);

4.不同路径2

题目链接：https://leetcode-cn.com/problems/unique-paths-ii/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
算法专题 - 图9
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
思路：跟上一题很像，但是有障碍物。继续五步走
1）dp表含义:dp[i][j]为到第i个位置和第j个位置的路径数
2）递推公式：这里的公式都一样，但是具有条件了，当没有障碍物时计算dp[i][j]的值。
3）初始化值：这里初始化值也不一样了，dp[i][0]这一行上如果遇到石头了，后面的值都是0，因为走不过去了嘛。
4）遍历顺序：还是一样的。
5）举例子

  1.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  2.         int m = obstacleGrid.length;
  3.         int n = obstacleGrid[0].length;
  4.         int[][] dp = new int[m][n];
  5.         for(int i = 0; i < m; ++i){
  6.             if(obstacleGrid[i][0] == 1){
  7.                 break;
  8.             }
  9.             dp[i][0] = 1;
  10.         }
  11.         for(int j = 0; j < n; ++j) {
  12.             if (obstacleGrid[0][j] == 1) {
  13.                 break;
  14.             }
  15.             dp[0][j] = 1;
  16.         }
  17.         for(int i = 1; i < m; ++i){
  18.             for(int j = 1; j < n; ++j){
  19.                 if(obstacleGrid[i][j] == 1){
  20.                     continue;
  21.                 }
  22.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  23.             }
  24.         }
  25.         return dp[m-1][n-1];
  26.     }

总结：这道题是有条件的动态规划，我踩了两个陷阱，第一行和第一列初始话的时候只是把障碍点的dp值设为0，其他点还是1，殊不知遇到障碍后面的值都是0。第二个陷阱是判断那里，我还在用if(dp[i][j] == 0)来看要不要计算算下去，是不是傻啊，我这一步就是要计算dp[i][j]，我都还没计算你就给我判断了？

5.整数拆分

https://leetcode-cn.com/problems/integer-break/
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1: 输入: 2 输出: 1
\解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2: 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 说明: 你可以假设 n 不小于 2 且不大于 58。
思路：一开始我想用递归做的，结果你知道的，超时。
开始吧，五步走：
1）确定dp[i]的含义：第i个值的组合成乘积最大。
2）递推公式：dp[i] = max(dp[i],max(dp[i-j]j,(i-j)j))这里要说一下里面那个max，第i个元素可以分成i-j和j，或者dp[i-j]*j这里相当于又把i-j给划分了，不过这里表里面的值直接就是i-j划分组合的最大值，有点贪心算法的味道了。
3）确定初始值，dp[2]=1呀。
4）遍历顺序，从前向后
5）举例子

  1.     public int integerBreak(int n) {
  2.         int[] dp = new int[n+1];
  3.         dp[2] = 1;
  4.         for(int i = 3; i <= n; ++i){
  5.             for(int j = 1; j < i-1; ++j){
  6.                 //里面最大是比的是把i拆分成i-j和j两个数相乘和拆成j*和i-j继续拆解的组合中的最大值
  7.                 dp[i] = Math.max(dp[i],Math.max(dp[i-j]*j,(i-j)*j));
  8.             }
  9.         }
  10.         return dp[n];
  11.     }

总结：这道题关键点在于dp[i]的含义是啥，一开始我就没想明白，还要递推公式那里设计一个剪枝问题，直接把每个元素的最大值给存储起来了，不用再去细分。

6.不同的二叉树

https://leetcode-cn.com/problems/unique-binary-search-trees/
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例:
算法专题 - 图10
思路:一个节点的时候只要一种情况；
两个节点的时候有两种情况。
算法专题 - 图11
仔细观察n=3的情况，当1为根节点的时候，左右子节点的结构跟n=2的时候两种情况一样，
2为跟节点的时候，左右子节点只有一个，结构跟n=1的情况一样。
3为根节点的时候，左子节点有两个元素，结构也跟n=2的时候一样。
所以可以推断dp[3]=dp[2]dp[0]+dp[1]dp[1]+dp[0]dp[2]。
动规五步走：
1）确定dp[i]含义：有i个节点时的组合个数。
2）推导公式：dp[i] += dp[j-1]dp[i-j]；j-1是j为头结点时左边子节点的个数，i-j是右边子节点的个数。
3）初始化值，dp[0] = 1;
4）遍历顺序，从前向后
5）举例

  1.     public int numTrees(int n) {
  2.         int[] dp = new int[n+1];
  3.         dp[0]  = 1;
  4.         for(int i = 1; i <= n; ++i){
  5.             for(int j = 1; j <= i;++j){
  6.                 dp[i] += dp[j-1]*dp[i-j];
  7.             }
  8.         }
  9.         return dp[n];
  10.     }

总结：动态规划也太秒了吧，记录不同个数的形态都是一样的，只要考虑不同节点作为根节点的情况就好了。

7.背包问题01

有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划思路：
1）确定初始化数组dp[i][j]含义，i是第i个物品，j是背包容量，值为有第i个物品放入背包容量为j的背包中的最大价值。例子dp[0][2]就是第0个物品放入背包容量为2的背包中，dp[1][2]就是第1个物品放入背包容量为2的背包中。其最大值可能是物品0和物品1的总价值，也有可能是物品0或者物品1的价值，这取决于背包能否放得下。
2）递推公式： 有两种情况，
第一种是第i个物品放不下容量为j的背包中，推导公式为dp[i][j]=dp[i-1][j]，和前一个物品放入容量为j的背包的情况一样。
第二种是第i个物品放得下容量为j的背包中，推导公式为dp[i][j]=dp[i-1][j-weiht[i]]+value[i]
表示第i-1个物品在背包容量j-weight[i]处的最大值，再加上当前物品的价值。
所以推导公式为dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
3）初始化值，dp[i][0]=0；dp[0][j] = value[0]，j>=weight[0]
4）遍历顺序，从前向后
5）举例
举例.jpg

  1.     public int package01(int[] weight,int[] value,int capacity){
  2.         //goods[0][0]第0个物品的重量   goods[0][1]第0个物品的价值
  3.         //dp[i][j]是拿第i个物品，j是背包的最大容量，值为价值总和最大是多少
  4.         int goodsNum = weight.length;
  5.         int[][] dp = new int[goodsNum][capacity+1];
  6.         //dp[i][0]初始为0,dp[0][j]=value[0];
  7.         for(int k = weight[0]; k < capacity+1; ++k){
  8.             if(weight[0] <= k){
  9.                 dp[0][k] = value[0];
  10.             }
  11.         }
  12.         //递推公式：有两种情况，1）dp[i][j]=dp[i-1][j]：背包重量为j时不放物品i，因为放不下，所以价值总和和i-1物品放j重量背包一样
  13.         //                  2）dp[i][j]=dp[i-1][j-weight[i]]+value[i] 背包重量为j时放得下物品i，并放入
  14.         // 所以递推公式是：dp[i][j] = max(dp[i-1][j],dp[i-1][weight[i]]+value[i])
  15.         for(int i = 1; i < goodsNum; ++i){
  16.             for(int j = 1; j <= capacity; ++j){
  17.                 if(j < weight[i]){
  18.                     dp[i][j] = dp[i-1][j];
  19.                 }else {
  20.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  21.                 }
  22.             }
  23.         }
  24.         return dp[goodsNum-1][capacity];
  25.     }

总结：这道题的难点在于搞明白dp表的含义，还有i,j的含义，递推公式也有点难度，dp值为放入第i个物品时或不放第i个物品时的最大值，放下第i个物品不一定表示在i-1物品的基础上加i物品，只是单纯的表示加了i物品，有几个物品出去了不关心。

8.分割等和子集（背包01变形）

链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/
题目难易：中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路：该问题的解是要找到一个组合，其和加起来为sum/2。
那么这和背包问题有什么联系呢？背包的最大容量为sum/2，而物体重就是数组元素nums，价值也是数组元素。
1）确定dp表的含义，dp[j]表示背包重量为j的情况下的能背的最大价值。
2）推导公式dp[j] = max(d[j],dp[j-nums[i])+nums[j])
两种情况，能放进来放下，你也许有疑问，肯定放进来的值大呀，不一定，这里有可能是先丢几件再放进来；还有干脆不放进来。看谁的大。
3）初始化，dp[0]=0，容量为0装的东西也为0。
4）遍历顺序：外层前向，内层后向。为什么要后向呢？前向会叠加一些内容。比如我放第一件物品，重量为1，dp[0]=0，dp[1]=1，dp[2]=2，实际上dp[2]应该为1，后向遍历不会出现这个问题。
5）举例

  1.     public boolean canPartition(int[] nums) {
  2.         int sum = 0;
  3.         for(int i = 0; i < nums.length; ++i){
  4.             sum += nums[i];
  5.         }
  6.         if(sum % 2 == 1){
  7.             return false;
  8.         }
  9.         sum = sum / 2;
  10.         int[] dp = new int[sum+1];
  11.         for(int i = 0; i < nums.length; ++i){
  12.             for(int j = dp.length-1; j >= nums[i]; --j){
  13.                 dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
  14.             }
  15.         }
  16.         if(dp[sum] == sum){
  17.             return true;
  18.         }
  19.         return false;
  20.     }

总结：背包01问题有三个东西，背包容量，物品重量，还有物品价值，这道题不仔细看真看不出来这是背包问题，这道题物品重量等于物品价值。
注意：完全背包问题也是同样的解法，不过遍历顺序变了一下

  1.         for(int i = 0; i < nums.length; ++i){
  2.             for(int j = nums[i]; j <= dp.length-1; ++j){
  3.                 dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
  4.             }
  5.         }

这里遍历顺序变了，假设第一个物品的时候在遍历的时候，加入物品重量为3，dp[3]~dp[5]肯定也是3，但是dp[6]就等于6了，这样相当于放了两个物品1。