一.网格图DFS

适用于需要计算连通块个数、大小的题目

1.岛屿数量

        给你一个由 1(陆地) 和 0（水）组成的二维网格，请你计算网格中岛屿的数量

        岛屿总是被水包围，并且每座岛屿只能由水平方向和\或竖直方向上相邻的陆地连接形成

        此外，你可以假设该网格的四条边均被水包围

        

     

class Solution {
    public int numIslands(char[][] grid) {
        /**
            插旗法：
            真他妈牛逼，看了下题解真不是人想出来的
            也就是说从起点开始，从四个方向开始遍历，直到发现边界就停止
            边界：为0，或者到头了，或者已经被插旗
            这样只要是起点能连通的位置都会被插旗，剩下的就是隔着0的区域访问不到
            那么就相当于当前这一大块就是一个岛屿
            然后继续寻找下一个岛屿
         */
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                //从[0,0]开始作为起点进行插旗
                if (grid[i][j] == '1') {
                    dfs(i, j, grid);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int i, int j, char[][] grid) {
        //边界问题
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length 
                || grid[i][j] != '1') {
            return;
        }
        //重点：将当前节点插旗，变为不为1的数
        grid[i][j] = '0';
        //开始四个方向进行dfs
        //上
        dfs(i - 1, j, grid);
        //下
        dfs(i + 1, j, grid);
        //左
        dfs(i, j - 1, grid);
        //右
        dfs(i, j + 1, grid);
    }    
}

2.岛屿的最大面积

        给你一个大小为 m x n 的二进制矩阵 grid

        岛屿是由一些相邻的 1(土地)构成的组合，这里的相邻要求两个1必须在水平或者竖直的四个

        方向上相邻，你可以假设grid的四个边缘都被0(水)包围

        岛屿的面积是岛上值为1的单元格的数目

        请计算grid的最大岛屿面积，如果没有岛屿，请返回0

     

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        //插旗法 比上一题难一点 要算面积
        int sum = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    sum = Math.max(sum, dfs(i, j, grid));
                }
            }
        }
        return sum;
    }

    private int dfs(int i, int j, int[][] grid) {
        //边界问题一订要定义好 不然会越界
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
            return 0;
        }
        int sum = 0;
        grid[i][j] = 2;
        sum++;  //自身
        sum += dfs(i - 1, j, grid); //上
        sum += dfs(i + 1, j, grid); //下
        sum += dfs(i, j - 1, grid); //左
        sum += dfs(i, j + 1, grid); //右
        return sum;
    }
}

  3.水域大小

        你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔

        高度，若值为0则表示水域，由垂直、水平或者对角连接的水域为池塘，池塘的大小是指

        相连的水域的个数，编写一个算法来计算矩阵中所有池塘的大小，返回值需要从小到大

        排序

class Solution {
    public int[] pondSizes(int[][] land) {
        //我草了 还有对角线 想想对角线怎么处理？
        //对角线 有4个呢 那就是8个方向去遍历咯
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[i].length; j++) {
                if (land[i][j] == 0) {
                    list.add(dfs(i, j, land));
                }
            }
        }
        int[] arr = new int[list.size()];
        list.sort((a, b) -> a - b);
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    private int dfs(int i, int j, int[][] land) {
        //边界问题
        if (i < 0 || i >= land.length || j < 0 || j >= land[0].length || land[i][j] != 0) {
            return 0;
        }
        int sum = 0;
        land[i][j] = 1;
        sum++;
        //上下左右，左上，左下，右上，右下
        sum += dfs(i - 1, j, land);
        sum += dfs(i + 1, j, land);
        sum += dfs(i, j - 1, land);
        sum += dfs(i, j + 1, land);
        sum += dfs(i - 1, j - 1, land);
        sum += dfs(i + 1, j - 1, land);
        sum += dfs(i - 1, j + 1, land);
        sum += dfs(i + 1, j + 1, land);
        return sum;
    }
}

二.动态规划DP

动态规划解题思路：

        1.寻找子问题

                寻找定义子问题，如果可以把原问题变成一个和原问题相似、规模更小

                的子问题，这种情况就可以用递归来解决

        2.递归怎么写

                状态定义与状态转移方程：

        3.递归+记录返回值=记忆化搜索

                因为在递归中，有着大量的重复递归调用(递归入参相同)，由于递归函数都是幂等的，

                同样的入参无论计算多少次结果都是一样的，所以我们可以用记忆化搜索来优化，

                就是将同样入参的计算结果放到缓存中，优先从缓存中拿结果，没有在递归

        4.1：1翻译成递推

                既我们可以去掉递归中的递，只保留归的部分，即自底向上计算

        5.空间优化

                一般dp问题，都是只会用到前面几个状态，之前已经计算过的状态在后面是永远不会

                再用了的，所以我们只需要知道比如上一个状态和上上一个状态即可               

1.爬楼梯

        假设你正在爬楼梯，需要 n 阶你才能到达楼顶

        每次你都可以爬 1 或者2个台阶，你有多少种不同的方式可以爬到楼顶呢？

        第一种解法：这个解法如果数据量大的话往往会超时    

class Solution {
    public int climbStairs(int n) {
        /**
            如果最后一步是爬了1个台阶 那么首先要爬到n-1台阶上
            如果最后一步是爬了2个台阶，那么首先要爬到n-2台阶上
            所以 而爬到n-1和n-2是两种不同的方法 所以
            dfs(n) = dfs(n - 1) + dfs(n - 2)
         */

        return dfs(n);
    }

    private int dfs(int n) {
        if (n <= 1) return 1;   //边界问题 0 和1
        return dfs(n - 1) + dfs(n - 2);
    }
}

        第二种解法：+缓存

class Solution {
    public int climbStairs(int n) {
        /**
            如果最后一步是爬了1个台阶 那么首先要爬到n-1台阶上
            如果最后一步是爬了2个台阶，那么首先要爬到n-2台阶上
            所以 而爬到n-1和n-2是两种不同的方法 所以
            dfs(n) = dfs(n - 1) + dfs(n - 2)
            为了边界问题，0和1因为爬到0和1个台阶都是只有1种方式
            所以初始化dfs(0) dfs(1) = 1 然后公式演变成
            dfs(n + 2) = dfs(1) + dfs(0)
         */
        Map<Integer, Integer> map = new HashMap<>();
        return dfs(n, map);
    }

    private int dfs(int n, Map<Integer, Integer> map) {
        if (n <= 1) return 1;   //边界问题 0 和1
        if (map.get(n) != null) return map.get(n);
        int num = dfs(n - 1, map) + dfs(n - 2, map);
        map.put(n, num);
        return num;
        //这个方式会超时 因为每次都是递归了2遍 变成了 n^2次了 增加一个缓存
        // return dfs(n - 1) + dfs(n - 2);
    }
}

        第三种解法：继续优化，1：1翻译成递推

        dfs(i) = dfs(i - 1) + dfs(i - 2)，那么我们可以定义成这样

        f[i] = f[i - 1] + f[i - 2]，之前是递归计算每个状态，现在是枚举计算每个状态

        初始值f[0] = f[1] = 1，翻译自递归边界dfs(0) = 1,dfs(1) = 1

        f[n] 翻译自dfs(n)       

class Solution {
    public int climbStairs(int n) {
        /**
            1.定义子问题
                假设最后一次是爬1个台阶，那么就是爬到n-1需要多少种方式
                假设最后一次是爬2个台阶，那么就是爬到n-2需要多少种方式
                最后爬到n的总方式是 上面两种方式之和 
                即 fn = fn-1 + fn-2
                但是在这过程种很多都是会重复计算 那么用一个缓存来记录算过的值
         */
        // int[] cache = new int[n + 1];
        // return dp(n, cache);

        //用逆推 0和1的时候方法是确定的
        int[] dp = new int[n + 1];
        dp[0] = 1; 
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    // private int dp(int n, int[] cache) {
    //     if (n <= 1) return 1;   //0和1个台阶的时候就只有一种方法
    //     if (cache[n] != 0) return cache[n];
    //     int num = dp(n - 1, cache) + dp(n - 2, cache);
    //     cache[n] = num;
    //     return num;
    // }
    
}

第四种解法：继续空间优化

因为计算当前值只需要知道上一个状态和上上一个状态，所以每次只保留这两个变量即可

class Solution {
    public int climbStairs(int n) {
        /**
            分析子问题，假设最后一步是1各台阶，那么爬到n-1个台阶的方法就是dfs(n-1)
            最后一步是2个台阶，爬到n-2个台阶的方法就是n-2
            最后总共有 fds(n-1)+dfs(n-2)种方法
            那么运用缓存 因为在dfs过程中肯定会有重复计算的
            那么就是缓存中有的就不用计算了
            再优化，递推： 因为1个台阶和2个台阶的方法都是1种 
            再优化 n-1是上一个 n-2是上上一个 因为每次计算完上一个上上一个的值再接下来就不会用到
            所以每次就只使用这俩变量就可以了 
         */

        // int[] dp = new int[n + 1];
        // dp[0] = 1;
        // dp[1] = 1;
        // for (int i = 2; i <= n; i++) {
        //     dp[i] = dp[i - 1] + dp[i - 2];
        // }
        // return dp[n];
        //优化一下空间
        int dp0 = 1, dp1 = 1;
        for (int i = 1; i < n; i++) {
            int dpi = dp1 + dp0;
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }
}

2.使用最小花费爬楼梯

        给你一个整数数组 cost，其中cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你

        支付此费用，即可旋转向上爬一个或者两个台阶

        你可以选择从下标为 0 或者 1 的台阶开始爬楼梯

        请你计算并返回到达楼顶的最低花费

        

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        /**
            分析子问题
            当最后是爬一个楼梯时，那么就是爬到n-1的费用+当前n-1的费用
            同理，当最后是爬2个楼梯，那么就是n-2的费用+当前n-2的费用
            然后取两者最小值
            int min = Math.min(dfs(n-1) + cost[n-1], dfs(n-2) + cost[n-2])
            剩下的就是开始优化
                优化：加缓存
                优化：递推 因为dfs(n-1)其实就是fn-1 同时 f0和f1是已知的都是=0 因为可以从0或者1开始 
                int[] dp = new int[n+1]
                min = Math.min(dp[n-1] + cost[n-1], dp[n-2]+cost[n-2]) 
        
         */
        // int[] cache = new int[cost.length + 1];
        // Arrays.fill(cache, -1);
        // return dfs(cost, cache, cost.length);

        //进行递推 因为 f0 f1都是已知的
        // int n = cost.length;
        // int[] dp = new int[n + 1];
        // dp[0] = 0;
        // dp[1] = 0;
        // for (int i = 2; i <= n; i++) {  //为什么从2开始呢 因为按照题目来0和1都是已知的 那么肯定从未知的第一个台阶2开始
        //     dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        // }
        // return dp[n];

        //继续优化 dpi-1可以认为是上一个 dpi-2是上上一个 那么总是只需要这两个变量即可 
        //上一次的上一个和上上一个算完以后就不会再用了
        int dp0 = 0, dp1 = 0; //为什么是0 按照上面推理 因为可以从0或者1开始爬 所以到达0或者1不需要成本
        for (int i = 1; i < cost.length; i++) {
            int min = Math.min(dp1 + cost[i], dp0 + cost[i - 1]);
            dp0 = dp1;
            dp1 = min;
        }
        return dp1;

        // int f0 = 0, f1 = 0;
        // for (int i = 1; i < cost.length; i++) {
        //     int fn = Math.min(f1 + cost[i], f0 + cost[i - 1]);
        //     f0 = f1;
        //     f1 = fn;
        // }
        // return f1;
    }

    // private int dfs(int[] cost, int[] cache, int n) {
    //     if (n <= 1) return 0;
    //     if (cache[n] != -1) return cache[n];
    //     cache[n] = Math.min(dfs(cost, cache, n - 1) + cost[n - 1], dfs(cost, cache, n - 2) + cost[n - 2]);
    //     return cache[n];
    // }
}

   3.打家劫舍

        你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃

        的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两件相邻的房屋在同一

        晚上被小偷闯入，系统会自动报警

        给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报的情况下，一夜

        之内能够偷窃到的最高金额

class Solution {
    public int rob(int[] nums) {
        /**
            最后一个房子偷不偷 下标从0开始
            偷 那么就是fn-2 +hn-1 前n-2个房子+最后一间房子的金额 因为索引从0开始 n-1就是最后一间房
            不偷 那就是fn-1  
            然后就是计算这俩最高值 max = Math.max(f(n-2) + h(n-1), f(n-1));
            然后换算
        
         */

        int n = nums.length;
        // int[] dp = new int[n + 1];  //从0开始
        // dp[0] = 0;
        // dp[1] = nums[0];
        // for (int i = 2; i <= n; i++) {
        //     dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        // }
        // return dp[n];
        //空间优化 
        // int dp0 = 0, dp1 = nums[0];
        // for (int i = 2; i <= n; i++) {
        //     int max = Math.max(dp1, dp0 + nums[i - 1]);
        //     dp0 = dp1;
        //     dp1 = max;
        // }
        // return dp1;

        //再优化
        int dp0 = 0, dp1 = 0;
        for (int x : nums) {
            int dp = Math.max(dp1, dp0 + x);
            dp0 = dp1;
            dp1 = dp;
        }
        return dp1;
    }
}

三.贪心

1.重新分装苹果

        给你一个长度为n的数组 apple 和另一个长度为 m 的数组 capacity

        一共有 n 个包裹，其中第 i 个包裹中装着 apple[i]个苹果，同时，还有 m 个箱子，第 i 个

        箱子的容量为 capacity[i] 个苹果，请你选择一些箱子来将这 n 个包裹中的苹果重新分装

        到箱子中，返回你需要选择的最小箱子数

        注意：同一个包裹中的苹果可以分装到不同的箱子中

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        //妙啊 贪心 这题目没有说输出箱子的index 只是计算个数
        //而且1个包裹里的苹果可以放到不同箱子里 所以从大到小排序箱子
        //直到装完苹果为止
        int appleSum = 0;
        for (int num : apple) {
            appleSum += num;
        }
        Arrays.sort(capacity);
        int m = capacity.length;
        int i = m - 1;
        while (appleSum > 0) {
            appleSum -= capacity[i--];
        }
        return m - i - 1;
    }
}