未命名分组 - DP-贪心-回溯 - 《数据结构 · Leetcode · SQL · 刷题笔记》

动态规划

剑指 Offer 49. 丑数

可以使用 3个指针的方法，因为对于每一个丑数来说，都是由前面的数字 x2,3,5 来组成的。所以状态转移的方程就是，取三个指针对应的数字的最小值。对应的哪个数++；

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        int a = 0,b = 0,c = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int q = dp[a]*2;
            int w = dp[b]*3;
            int e = dp[c]*5;
            dp[i] = Math.min(q,Math.min(w,e));
            if(q == dp[i])a++;
            if(w == dp[i])b++;
            if(e == dp[i])c++;
        }
        return dp[n-1];
    }
}

91. 解码方法

思路：
最先想到的方法就是挨个来遍历一下字符串里面的数字。dp[i]代表[0,i]中的可以编码的总数。
如果和前面组成的数值在 [1,26]里面的话，那就设置dp[i] = dp[i-1]+dp[i];

主要的情况有以下的几种：

若s[i] == 0
- s[i-1] == 2 或1 那dp[i] = dp[i-1]+dp[i-2]; 不然就是一个无效的字符串，返回0；
若s[i-1] ==1 则dp[i] = dp[i-1]+dpi-2
若s[i-1] ==2 并且 s[i] 在1-6之间则 dp[i] = dp[i-1]+dp[i-2];
最后的情况就是dp[i] = dp[i-1] （就是没有什么变化）

class Solution {
    public int numDecodings(String s) {
        int[] dp = new int[s.length()+1];
        if(s.charAt(0) != '0'){
            dp[0] = 1;
            dp[1] = 1;
        }
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == '0'){
                if(s.charAt(i-1) =='1'|| s.charAt(i-1)=='2'){
                    dp[i+1] = dp[i-1];
                }else{
                    return 0;
                }         
            }else if(s.charAt(i-1) =='1'){
                dp[i+1] = dp[i]+dp[i-1];
            }else if(s.charAt(i-1)=='2' && s.charAt(i)>='1'&&s.charAt(i)<='6'){
                dp[i+1] = dp[i]+dp[i-1];
            }else{
                dp[i+1] = dp[i];
            }
        }
        return dp[s.length()];
    }
}

279. 完全平方数

思路一：
这道题使用的动态规划，DP[i] 代表着 i 这个数字组成和的完全平方数的最小个数。想法是这样的，对于每一个数 i 我先判断一下他是不是完全平方数，如果是的话，dp[i] = 1 如果不是的话，我们需要遍历一下存完全平方数的set，遍历一下里面所有的结果。找到里面的最小值。

    public int numSquares(int n) {
        int[] dp = new int[n+1];
        HashSet<Integer> set = new HashSet<>();
        dp[1] = 1;
        set.add(1);
        for (int i = 2; i <= n; i++) {
            if(Math.pow((int)Math.sqrt(i),2)==i){
                dp[i] = 1;
                set.add(i);
            }else {
                dp[i] = Integer.MAX_VALUE;
                for (int j:set){
                    dp[i] = Math.min(dp[i-j]+dp[j],dp[i]);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

思路2：
前面的思路中，我额外的使用了一个set来存放完全平方数，这其实可以使用一个 j*j <= i 这样的一个简单的表达式来代替，dp[0] 按照要求，为0 ；

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

343. 整数拆分

对于一个整数的拆分，可以有以下的想法：

public int integerBreak(int n) {
        int[] dp =  new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <=n; i++) {
            for (int j = 1; j <= i/2; j++) {
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

64. 最小路径和

简单DP，就取一下左边和上边的最小值加一下就好了。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0]+grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1]+grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <n; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        // for (int i = 0; i < m; i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        return dp[m-1][n-1];
    }
}

96. 不同的二叉搜索树

又是一道DP的题目 = =：
思路：

这道题如何去推测出这个公式，这其实是非常的难的= = 从这个题目想到用这样的公式去推测这个答案。

class Solution {
    public int numTrees(int n) {
        int [] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <=n; i++) {
            for (int j = 1; j <=i; j++) {
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}

97. 交错字符串

其实这个问题就是一个地下城的包装版本。对于这个格子而言，只能从上面说着左边过来。寻找一条这样的路径，能否到到右下角。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if(n+m!=s3.length()){
            return false;
        }
        boolean dp[][] = new boolean[s1.length()+1][s2.length()+1];
        dp[0][0] = true;
        for (int i = 1; i <=m; i++) {
            if(dp[i-1][0]){
                dp[i][0] = s1.charAt(i-1) == s3.charAt(i-1);
            }
        }

        for (int i = 1; i <=n; i++) {
            if(dp[0][i-1]){
                dp[0][i] = s2.charAt(i-1) == s3.charAt(i-1);
            }
        }

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                dp[i][j] = (dp[i-1][j]&&s3.charAt(i+j-1)==s1.charAt(i-1))||(dp[i][j-1] && s3.charAt(i+j-1)==s2.charAt(j-1));
            }
        }

        // for (int i = 0; i < dp.length; i++) {
        //     System.out.println(Arrays.toString(dp[i]));
        // }
        return dp[s1.length()][s2.length()];
    }
}

120. 三角形最小路径和

这其实是一道动态规划的题目。但是需要从下开始遍历往上。直接构建一个n+1*n+1的网络。从底层往上来计算 dp[i][j] = min(dp[i+1][j]+dp[i+1][j+1])

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n+1][n+1];
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

174. 地下城游戏

还是一道DP的题目，但是我们需要从后往前进行遍历。对于最后的一列和一行，状态转移方程为 Math.max(1,dp[i+1][n-1]-dungeon[i][n-1]);
对于正常的那些地方，为
dp[i][j] = Math.max(1,Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);


class Solution {
    public int calculateMinimumHP(int[][] dungeon) {

        int[][] dp = new int[dungeon.length][dungeon[0].length];

        // think about the dp[i][j] mean the min health
        // for get this index;

        int m = dungeon.length - 1;
        int n = dungeon[0].length - 1;

        dp[m][n] = dungeon[m][n] < 0 ? 1-dungeon[m][n] : 1;
        for (int i = m - 1; i >= 0; i--) {
            dp[i][n] = Math.max(1, -dungeon[i][n] + dp[i + 1][n]);
        }
        for (int i = n - 1; i >= 0; i--) {
            dp[m][i] = Math.max(1, -dungeon[m][i] + dp[m][i + 1]);
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }

        return dp[0][0];

    }
}

309. 最佳买卖股票时机含冷冻期

需要建立一个dp[length][3]的数组，其中0 表示持有
1表示可买可卖 2 表示处于冷冻期。
可以有以下的图表：

package Leetcode;

public class Solution309 {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) return 0;
        int[][] dp = new int[prices.length][3];
        dp[0][0] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][2],dp[i-1][1]);
            dp[i][2] = dp[i-1][0]+prices[i];
        }
        int res = Math.max(dp[prices.length-1][1], dp[prices.length-1][2]);
        return res;
    }
}

62. 不同路径

思路: 其实和63题的思路是一样的，中间少了障碍物的阻止。更新DP状态

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i-1][0];
        }

        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j]+dp[i][j-1]; 
            }
        }
        return dp[m-1][n-1];
    }
}

63. 不同路径 II

思路：DP 每一个位置是上面一个和左边的和。需要把最上面的一层和最左边的一层先做一个处理。

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // dp数组代表 i，j 位置上的不同路径的数量
        int[][] dp = new int[m][n];
        if(obstacleGrid[0][0] != 1){
            dp[0][0] = 1;
        }
        if(dp[0][0] ==0)return 0;

        for (int i=1;i<n;i++){
            if(obstacleGrid[0][i]!=1){
                dp[0][i] = dp[0][i-1];
            }
        }


        for (int i=1;i<m;i++){
            if(obstacleGrid[i][0]!=1){
                dp[i][0] = dp[i-1][0];
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                    System.out.println(dp[i][j]);
                }

            }
        }
        return dp[m-1][n-1];
    }
}

718. 最长重复子数组

定义DP数组

看到阵DP呆的数组之后就可以马上写出代码了

package Leetcode;

import java.io.FileInputStream;

public class Solution718 {
    public int findLength(int[] A, int[] B) {
        int an = A.length;
        int bn = B.length;
        int res = 0;
        int[][] dp = new int[an][bn];
        for (int i = 0; i < an; i++) {
            for (int j = 0; j < bn; j++) {
                if(A[i] == B[j]){
                    if(i-1>-1&&j-1>-1&&dp[i-1][j-1]!=0){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else {
                        dp[i][j] = 1;
                    }
                }
                res = Math.max(res,dp[i][j]);
            }
        }
        return res;
    }

}

面试题 17.13. 恢复空格

这道题和单词拆分的思路有一点像。但是这里使用的Trie来做。并且需要记录的的是未识别的字符数。
dp的思路和前文是有一点像的。
https://leetcode-cn.com/problems/re-space-lcci/solution/hui-fu-kong-ge-by-leetcode-solution/

class Solution {
public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();

        Trie root = new Trie();
        for (String s: dictionary){
            root.insert(s);
        }
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i-1]+1;

            Trie cur = root;
            for (int j=i;j>=1;--j){
                int index = sentence.charAt(j-1) - 'a';
                if(cur.next[index] == null){
                    break;
                }else if(cur.next[index].isEnd){
                    dp[i] = Math.min(dp[i],dp[j-1]);
                }
                if(dp[i] == 0){
                    break;
                }
                cur = cur.next[index];
            }
            // System.out.println(dp[i]);
        }
        return dp[n];
    }

class Trie{
    public Trie[] next;
    public boolean isEnd;

    public Trie(){
        next = new Trie[26];
        isEnd = false;
    }
    public void insert(String s){
        Trie cur = this;

        for (int i=s.length()-1;i>=0;i--){
            int index = s.charAt(i) - 'a';
            if(cur.next[index] == null){
                cur.next[index] = new Trie();
            }
            cur = cur.next[index];
        }
        cur.isEnd = true;
    }
}
}

139. 单词拆分

https://leetcode-cn.com/problems/word-break/solution/dong-tai-gui-hua-python-dai-ma-by-liweiwei1419-2/

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>();
        int len = s.length();
        boolean[] dp = new boolean[len];
//        数据预处理。
        for (String str:wordDict){
            set.add(str);
        }


        for (int i =0;i<len;i++){
            if(set.contains(s.substring(0,i+1))){
                dp[i] = true;
                continue;
            }

            for (int j=0;j<i;j++){
                if(dp[j]&& set.contains(s.substring(j+1,i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return  dp[len-1];
    }
}

剑指 Offer 47. 礼物的最大价值

思路：本来是用DFS写的一道题目，写出来结果超时了。看了答案之后发现是dp的题目，grid[i][j] 的数值只和grid[i-1][j]和grid[i][j-1] 有关，所以状态转移方程其实非常的简单。

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if(i ==0 && j==0) continue;
                if(i == 0) dp[i][j] = dp[i][j-1]+grid[i][j];
                else if(j==0) dp[i][j] = dp[i-1][j]+grid[i][j];
                else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
                }

            }
        }
        return dp[m-1][n-1];
    }
}

面试题42. 连续子数组的最大和

dp 数组的每一位代表以i为结尾的子串的大小。
如果dp[i-1]<0 直接放弃，不如不要
如果dp[i-1]>0 dp[i] = dp[i-1]+num[i];

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res= Integer.MIN_VALUE;

        for (int i=1;i<nums.length;i++){
            if(dp[i-1]<0){
                dp[i] = nums[i];
            }else {
                dp[i] = dp[i-1]+nums[i];
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

面试题46. 把数字翻译成字符串

说实话，这道题的转移方程我有一点不会写。直观的答案 DP-贪心-回溯 - 图17
翻译成为代码：

    public int translateNum(int num) {
        String s = String.valueOf(num);
        System.out.println(s);
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i=2;i<dp.length;i++){
            int n = (s.charAt(i-2)-'0')*10+s.charAt(i-1)-'0';
            if(10<=n&&n<=25){
                dp[i] = dp[i-1]+dp[i-2];
            }else {
                dp[i] = dp[i-1];
            }
        }
        return dp[s.length()];
    }

198. 打家劫舍

定义DP数组 Dp[i]的意思是到i为止的最大的收益

所以可以得到

dp[1] = nums[0]
dp[2] = nums[1]

dp[i] = max(dp[i-2],dp[i-3])+nums[i-1];

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];
        if(nums.length<1) return 0;
        if(nums.length ==1) return nums[0];
        if(nums.length ==2) return Math.max(nums[0],nums[1]);
        dp[1] = nums[0];
        dp[2] = nums[1];


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

        }
        for(int i:dp){
            res = Math.max(res,i);
        }
        return res;

    }
}

213. 打家劫舍 II

这道题的一个变化就是数变成一个环形的数组，就是说第一个和最后一个是连接起来的。我们可以这么处理

package Leetcode;

public class Solution213 {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n== 1){
            return nums[0];
        }
        return Math.max(robRange(nums,0,n-2),robRange(nums,1,n-1));

    }

    private int robRange(int[] nums, int start, int end) {

        int n = nums.length;
        // dp[i] = x 表示：
        // 从第 i 间房子开始抢劫，最多能抢到的钱为 x
        // base case: dp[n] = 0
        int[] dp = new int[n + 2];
        for (int i = end; i >= start; i--) {
            dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
        }
        return dp[start];

    }
}

152. 乘积最大子数组

class Solution {
    public int maxProduct(int[] nums) {
        int[] dpMax = new int[nums.length];
        int[] dpMin = new int[nums.length];

        if(nums.length == 0)return 0;

        int res = nums[0];
        dpMax[0] = nums[0];
        dpMin[0] = nums[0];

        for(int i=1;i<nums.length;i++){
            dpMax[i] = Math.max(nums[i]*dpMax[i-1],Math.max(nums[i],dpMin[i-1]*nums[i]));
            dpMin[i] = Math.min(nums[i]*dpMin[i-1],Math.min(nums[i],dpMax[i-1]*nums[i]));

            res = Math.max(dpMax[i],res);

        }

        return res;

    }
}

221. 最大正方形

这道题我没有想到是动态规划的思路。 dp数组的意思是以 i j 为右下角的正方形的边长。取他的左上的三个数值。取最小值。

若某格子值为 1 ，则以此为右下角的正方形的、最大边长为：上面的正方形、左面的正方形或左上的正方形中，最小的那个，再加上此格。

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix.length<1) return 0;
        int[][] dp = new int[matrix.length+1][matrix[0].length+1];
        int max = 0;

        for(int i=1;i<=matrix.length;i++){
            for(int j=1;j<=matrix[0].length;j++){
                if(matrix[i-1][j-1] =='1'){
                    //遇到左上角的为1的时候才开始计算当前的地方有没有。
                    // dp[i][j] 为ij坐标的正方形的边长。
                    dp[i][j] = 1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
                    max = Math.max(max,dp[i][j]);
                }

            }
        }
        return  max*max;
    }
}

983. 最低票价

这道题思路需要按照他给你里的条件来。

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        if(days.length<1||costs.length!=3){
            return 0;
        }

        int[] dp = new int[days[days.length-1]+1];

        for(int day:days){
            dp[day] = Integer.MAX_VALUE;
        }

        dp[0] = 0;


        for (int i=1;i<dp.length;i++){
            if(dp[i] ==0){
                dp[i] = dp[i-1];
                continue;
            }

            int n1 = dp[i-1]+costs[0];
            int n2 = i>7?dp[i-7]+costs[1]:costs[1];
            int n3 = i>30?dp[i-30]+costs[2]:costs[2];

            dp[i] = Math.min(n1,Math.min(n2,n3));
        }
        return dp[days[days.length-1]];

    }
}

动态规划，每次小循环只用一种硬币。
若在一次for循环中处理四种情况(一个for里带四个硬币的处理情况)，每次计算新一项时，由于每次取的硬币是任意的，会出现对于不同的硬币取法，情况重复的现象。例如：n=15时，res[15] = 1(全1) + res[15 - 5] + res[15 - 10] = 7，但10 + 5和5 + 10是重复的。
每次小循环只用一种硬币可以避免重复，因为每次小循环中选用的硬币是固定的，在没有到对应硬币的循环前，表内记录对应的解必然不包含该硬币。例如：n=15时，四次：res[15]=0 -> res[15] = 0 -> res[15] = 2 -> res[15] = 6
实际上coins数组升序也不会影响结果。

class Solution {
    private final int mod = 1000000007;
    private final int[] coins = {1,5,10,25};
    public int waysToChange(int n) {
        int[] res = new int[n + 1];
        res[0] = 1;
        for(int coin : coins){
            for(int i = coin;i <= n;i++){
                res[i] = (res[i] + res[i - coin]) % mod;
            }
        }
        return res[n];

    }
}

70. 爬楼梯

其实就是斐波那契数列的变体

class Solution {
    public int climbStairs(int n) {
        // 1. dp 自底向上
        // 2. 递归实现
        if(n<2)return n;
        int p1 = 1;
        int p2 = 2;
        for(int i=3;i<=n;i++){
           int tmp = p1+p2;
           p1 = p2;
           p2 = tmp;
        }
        return p2;
    }
}

或者使用一个dp数组。

class Solution {
    public int climbStairs(int n) {
        // 1. dp 自底向上
// 2. 递归实现
        if(n ==1) return 1;
        if(n==2) return 2;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

72. 编辑距离

自底向上的解决这个问题。首先要看到，对于字符，我们有四种操作。用 i,j来分别代表word1 和word2 的相应的部分。一共有四种情况，
第一种是对应的字符是一样的。在这种情况下，i和j都需要像前走一位。
第二种情况是需要删除的操作。就是说i -1；
第三种情况是做添加的操作。j-1（匹配了）i不动
第四种情况是做替换的操作。 i-1 而且j-1 因为已经匹配到了。

那怎么确定要多少呢》我们需要判断一下里面的最小值。
采用自底向上的方法。需要设计一个Dp数组。

之后就可以编写代码了。

class Solution {
    public int minDistance(String word1, String word2) {
        int s1 = word1.length();
        int s2 = word2.length();
        int[][] dp = new int[s1+1][s2+1];

        for(int i =0;i<=s1;i++){
            dp[i][0]= i;
        }
        for(int j=0;j<=s2;j++){
            dp[0][j] = j;
        }

        for(int i=1;i<=s1;i++){
            for(int j=1;j<=s2;j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);

                }
            }
        }
        return dp[s1][s2];

    }

}

300. 最长上升子序列

思路：
这个是很典型的动态规划的题目。
可以使用动态规划的方法进行计算。我们可以假设n-1的数据已经得到了，内欧盟怎么去获得一下n位置的值呢？
dp数组我们这样定义：
dp【i】中的数据是nums【i】这个数据的最大上升子序列的值。这么看来，我们只需要对dp数组进行一个遍历，得到里面的最大值，+1就是我们n的数值了。

for(int j=0;j<i;j++){
    if(num[i]>num[j]){
    dp[i] = Math.max(dp[i],dp[j]+1);
    }
}

在外面套一层数据，就是我们所要找的数据了。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);

        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0;
        for(int i=0;i<dp.length;i++){
            res = Math.max(res,dp[i]);
        }
        return res;

    }
}

面试题 17.16. 按摩师

思路：
题目中的最优预约集合提醒使用动态规划的思路。
动态规划的话，我们需要考虑已下几点：
是否含有局部最优？
是否有重叠子问题？
写出状态转移方程。
这个题目的关键在于如何定义dp数组，里面的每一位是什么。
这里我们设置为 i为0-i位置上的最优预约集合时间。
当前的时间之和 i-2 和i-3相关。所以我们可以列出方程

之后我们就可以写代码了。

class Solution {
    public int massage(int[] nums) {
        if(nums == null || nums.length<1)return 0;
        if(nums.length ==1)return nums[0];
        if(nums.length ==2)return Math.max(nums[1],nums[0]);


        int[] res = new int[nums.length];
        res[0] = nums[0];
        res[1] = nums[1];
        res[2] = res[0]+nums[2];

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

    }
}

贪心

134. 加油站

暴力解法，从 i 开始遍历一圈，如果能回到开始的地方那就回掉i的坐标。不然就试一试下一个

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;

        for (int i = 0; i < len; i++) {
            int j = i;
            int remain = gas[i];

            while (remain-cost[j]>=0){
                remain = remain- cost[j]+gas[(j+1)%len];
                j = (j+1)%len;
                if(j ==i){
                    return i;
                }
            }
        }
        return -1;
    }
}

406. 根据身高重建队列

思路：
先按照身高从高到低进行排序，之后按照位置从小到大进行排序，之后按照位置自己插入就可以了。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o1[1]-o2[1];
                }else {
                    return o2[0]-o1[0];
                }
            }
        });
        LinkedList<int[]> res = new LinkedList<>();
        for(int[] i:people){
            res.add(i[1],i);
        }

        return res.toArray(new int[res.size()][2]);
    }
}

435. 无重叠区间

455. 分发饼干

思路
把数组排序一下，用两个指针指一下。如果不符合就下一个。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int kid = 0;
        int sug = 0;
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);        
        while (kid!=g.length&&sug!=s.length){
            if(s[sug]<g[kid]){
                sug++;
            }else {
                kid++;
                sug++;
                res++;
            }
        }
        return res;        

    }
}

122. 买卖股票的最佳时机 II

这道题的关键在于一天里面是可以连续的买卖的，所以计算一下当前的价格和昨天的价格，有得赚那就加到结果里面去。

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int tmp = 0;
        for (int i=1;i<prices.length;i++){
            tmp = prices[i]-prices[i-1];
            if(tmp>0){
                res+=tmp;
            }
        }
        return res;

    }
}

605. 种花问题

按照这道题的思路来。对于这个数组里面的每一个数，是有那么几种的。假如i位置上的是1 那么直接跳过。如果前一个位置是1，那没也不行。如果后一个位置上是1的话，那也是不行。根据题目写出代码

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        for (int i=0;i<flowerbed.length;i++){
            if(flowerbed[i] ==1){ //当前是1 不能种植
                continue;
            }
            if(i<flowerbed.length-1&&flowerbed[i+1]==1){// 后一个不能是1
                continue;
            }
            if(i>0&&flowerbed[i-1]==1){// 前一个不能是1
                continue;
            }
            flowerbed[i] = 1;
            n--;
        }
        return n<=0;
    }
}

860. 柠檬水找零

模拟题目的意思来写代码。付=如果给你的是5块，那就five++ 如果是给你的是10元，那就ten++，five-1.如果是20的话，就有多种情况，3个五块，和一个十块一个五块。每次的循环之后都判断一下是不是纸币不够用了。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0,ten = 0;
        for (int bill:bills){
            if(bill ==5){
                five++;
            }else if(bill ==10){
                ten++;
                five--;
            }else {
                if(ten>0&&five>0){
                    ten--;
                    five--;
                }else {
                    five-=3;
                }
            }
            if(five<0||ten<0){
                return false;
            }
        }
        return true;

    }
}

55. 跳跃游戏

解题思路：
如果某一个作为起跳点的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为起跳点。
可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
如果可以一直跳到最后，就成功了。

class Solution {
    public boolean canJump(int[] nums) {
        int start = 0;

        for(int i=0;i<nums.length;i++){
            if(start<i){
                return false;
            }
            start = Math.max(start,i+nums[i]);
        }
        return true;

    }
}

45 跳跃游戏II

这道题和前面的那道题的区别在于，这里需要记录一下我最少的步数。可以使用贪心的思路来做。假如第一个是2.我们就知道了这个能挑到的最远的距离是i+nums[i]。在这里的话就是里面的这个2. 我们知道1-2 的范围都可以跳到。开始开始遍历能到的范围里面可以到的最远的位置。比如里面有一个4 ，下标是1. 那么最远的距离就是1+4. 如果i==max。说明我们搜索到了当前的右边界。那就更新一下右边界。

class Solution {
    public int jump(int[] nums) {
        int maxPoint = 0;
        int step = 0;
        int max = 0;
        for(int i=0; i<nums.length-1;i++){
            maxPoint = Math.max(maxPoint,i+nums[i]);

            if(i==max){
                max = maxPoint;
               step++; 
            }
        }
        return step;

    }
}

回朔

回溯有三大题型：子集，组合，排列

回溯模板

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

子集

输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。
比如输入 nums = [1,2,3]，你的算法应输出 8 个子集，包含空集和本身，顺序可以不同：
[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]

组合

排列

37. 解数独

数独这道题需要3个数组来记录一下有没有在行列，块中使用过这个元素。其实就是本来只使用一个used数组来做记录，现在需要使用多个Used数组来记录一下。

package Leetcode;

import java.util.HashMap;

public class Solution37 {
    public void solveSudoku(char[][] board) {
        boolean[][] rowUsed = new boolean[9][9];
        boolean[][] colUsed = new boolean[9][9];
        boolean[][][] boxUsed = new boolean[3][3][9];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]!='.'){
                    int num = board[i][j]-'1';
                    rowUsed[i][num] = true;
                    colUsed[j][num] = true;
                    boxUsed[i/3][j/3][num] = true;
                }
            }
        }

        recusiveSolveSudoku(board,rowUsed,colUsed,boxUsed,0,0);
    }

    private boolean recusiveSolveSudoku(char[][] board, boolean[][] rowUsed, boolean[][] colUsed, boolean[][][] boxUsed, int row, int col) {
        if(row == board.length){
            row = 0;
            col++;
            if(col== board[0].length){
                return true;
            }
        }

        if(board[row][col] == '.'){
            for (int i = 0; i < 9; i++) {
                boolean canUsed = !(rowUsed[row][i]||colUsed[col][i]||boxUsed[row/3][col/3][i]);

                if(canUsed){
                    rowUsed[row][i] = true;
                    colUsed[col][i] = true;
                    boxUsed[row/3][col/3][i] = true;
                    board[row][col] = (char)(i+'1');
                    if(recusiveSolveSudoku(board,rowUsed,colUsed,boxUsed,row+1,col)){
                        return true;
                    }
                    board[row][col] = '.';
                    rowUsed[row][i] = false;
                    colUsed[col][i] = false;
                    boxUsed[row/3][col/3][i] = false;
                }
            }
        }else {
            return recusiveSolveSudoku(board,rowUsed,colUsed,boxUsed,row+1,col);
        }
        return false;
    }
}

39. 组合总和

思路就是常规的的回溯，遍历一下每一个选项

class Solution {
List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(target<=0){
            return res;
        }
        ArrayList<Integer> tmp = new ArrayList<>();
        dfs(candidates,target,0,0,tmp);
        return res;


    }

    private void dfs(int[] candidates, int target, int num, int index, ArrayList<Integer> tmp) {
        if(num>target){
            return;
        }
        if(num == target){
            res.add(new ArrayList<>(tmp));
        }
        for (int i = index; i < candidates.length; i++) {
            tmp.add(candidates[i]);
            dfs(candidates,target,num+candidates[i],i,tmp);
            tmp.remove(tmp.size()-1);
        }
    }
}

面试题34. 二叉树中和为某一值的路径

这道题的思路，我想到的方法就是回溯法。遍历一下里面的所有的节点。对于是null节点，返回，维护一个记录当前数据的i，和路径tmp。如果这个节点是叶子节点并且i== 目标值则将这个数据加入到结果里面。然后开始遍历下一层的节点。

/**
 * 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>> pathSum(TreeNode root, int sum) {
        int i = 0;
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> tmp = new LinkedList<>();
        backTrace(root,i,sum,res,tmp);
        return res;
    }
    private void backTrace(TreeNode root,int i,int sum,List<List<Integer>> res,LinkedList<Integer> tmp){
        if(root == null){
            return;
        }
        i+=root.val;
        tmp.add(root.val);
        boolean isLeaf = root.left==null && root.right==null;
        if(i ==sum&&isLeaf){
            res.add(new LinkedList<>(tmp));
        }
        if(root.left!=null){
            backTrace(root.left,i,sum,res,tmp);
            tmp.removeLast();
        }
        if(root.right!=null){
            backTrace(root.right,i,sum,res,tmp);
            tmp.removeLast();
        }
    }
}

77. 组合

这道题和括号生成有点像。采用回朔的思想。我们遍历一下这个数组，把当前的这个数放到tmp里面去。之后递归到下一层。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> ans = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {

        createNum(1,n,k);
        return res;

    }

    private void createNum(int begin,int n, int k) {

        if(ans.size()== k){
            res.add(new ArrayList(ans));// 注意一定要新建一个，不然放进去的都是一个ans的地址。

        }

        for(int i=begin;i<=n;i++){
            ans.add(i);
            createNum(i+1,n,k);//i+1 非常的关键
            ans.removeLast();// 回朔，取消刚刚的操作。
        }
    }
}

46. 全排列

思路：使用一个回朔的思路。逐层去向下遍历我们剩下的数据。直到数据遍历完了。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track =  new LinkedList<>();
        traceback(nums,track);
        return res;

    }
    private void traceback(int[] nums,LinkedList<Integer> track){
        if(track.size() == nums.length){
            res.add(new LinkedList<Integer>(track));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(track.contains(nums[i])){
                continue;
            }

            track.add(nums[i]);
            traceback(nums,track);
            track.removeLast();
        }
    }
}

47. 全排列 II

这道题的和46题很像，但是加了重复的元素。结果是不能重复的。
第一个想法是诗一个used数组来表示这个元素又没有访问过。有的话，直接跳过。但是这样的话，结果会重复。
把数组排序一下，可以判断一下

i>0 && num[i-1]==num[i] && !hasVisit(i) // 前一个节点因为刚刚回朔回来，需要是false
    不然的话，就会把第一次的也给省略了。

面试题38. 字符串的排列

这道题的思路和前面的47题其实是一样的，给定的字符串里面有重复的字符，但是需要的生成的结果不能有重复的结果，里面的剪枝思路是这样的：
如果数组里面的东西是一样的，并且上次刚好使用过这个字符，那就跳过。

class Solution {
    public String[] permutation(String s) {
        List<String> res = new ArrayList<>();
        LinkedList<Character> tmp = new LinkedList<>();
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        boolean[] isUsed = new boolean[s.length()];

        backTrace(ss,isUsed,res,tmp);
        return res.toArray(new String[res.size()]);
    }

    private void backTrace(char[] ss, boolean[] isUsed, List<String> res, LinkedList<Character> tmp) {
        if(tmp.size() == ss.length){
            StringBuilder sb = new StringBuilder();
            for (char s:tmp){
                sb.append(s);
            }
            res.add(sb.toString());
            return;

        }
        for (int i=0;i<ss.length;i++){
            if(isUsed[i])continue;
            if(i>0&& ss[i-1]==ss[i]&&isUsed[i-1])continue;

            isUsed[i] = true;
            tmp.add(ss[i]);
            backTrace(ss,isUsed,res,tmp);
            tmp.removeLast();
            isUsed[i] = false;
        }
    }
}

DP-贪心-回溯

动态规划

面试题 08.11. 硬币(没搞懂)

贪心

45 跳跃游戏II

回朔

回溯模板

子集

组合

排列