1.1、斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

public class T7 {
    public int Fibonacci(int n) {
        // 条件
        if (n <= 1) return n;
       	// 可以用自底向上的方法
        int pre2 = 0, pre1 = 1;
        int f = 0;
        for (int i = 2; i <= n; i++) {
            f = pre2 + pre1; // 如果动态规划，这个就是dp的公式
            pre2 = pre1;
            pre1 = f;
        }
        return f;
    }
}

1.2、跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。总得还是公式F(N)=F(N-1)+F(N-2)

public class T8 {
    public int JumpFloor(int target) {
        // 条件
        if (target <= 2) return target;
      	// 自底向上的方法
        int pre2 = 1, pre1 = 2;
        int sum = 0;
        for (int i = 3; i <= target; i++) {
            sum = pre2 + pre1; // 一样的道理， 和上面那道题的初始值不一样
            pre2 = pre1;
            pre1 = sum;
        }
        return sum;
    }
}

1.3、矩形覆盖

我们可以用2乘1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2乘1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？还是公式F(N)=F(N-1)+F(N-2)。

public class T10 {
    public int RectCover(int target) {
        // 条件
        if (target <= 2) return target;
      	// 自底向上
        int pre2 = 1, pre1 = 2;
        int sum = 0;
        for (int i = 3; i <= target; i++) {
            sum = pre2 + pre1; // 同理呀
            pre2 = pre1;
            pre1 = sum;
        }
        return sum;
    }
}

1.4、变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public int JumpFloorII(int target) {
    int[] dp = new int[target];
    Arrays.fill(dp, 1);  //快速填充数组值为1，每层都有直接一步到位的情形
    // 注意起始位置
    for (int i = 1; i < target; i++)
    // 开始跳
        for (int j = 0; j < i; j++)
        // 注意dp[i] 累计dp[j]
            dp[i] += dp[j];
    return dp[target - 1];
}

2. 最大子序和(1385)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        // 注意两个变量的初始化
        int preSum = nums[0];
        int maxSum = preSum;
        // 注意从1开始
        for (int i = 1; i < nums.length; i++) {
            // 注意这个条件
            preSum = preSum > 0 ? preSum + nums[i] : nums[i];
            maxSum = Math.max(maxSum, preSum);
        }
        return maxSum;
    }
}

3.1、股票的最大利润

>输入：[7,1,5,3,6,4]
>输出：5
>解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
    注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

>输入：prices = [7,6,4,3,1]
>输出：0
>解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return -1;
        int min = prices[0];
        int max = 0;
        // 从1开始
        for (int i = 1; i < prices.length; i++) {
            // 注意保持最小
            min = prices[i] < min ? prices[i] : min; 
            max = Math.max(max, prices[i] - min);  //即找出已经出现的最小值，每天都计算利润即可
        }
        return max;
    }
}

3.2 买卖股票的最佳时机 II

在上题基础上可以多次交易

>输入: [7,1,5,3,6,4]
>输出: 7
>解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

>输入: [1,2,3,4,5]
>输出: 4
>解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
    因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

class Solution {
    public int maxProfit(int[] prices) {
        // 贪心：只要我当前数比前一个数大， 就xxx
        int profit = 0;
        // 从1开始，因为下面的if
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) 
                profit += prices[i]- prices[i - 1];
        }
        return profit;
    }
}

4. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

>输入：[1,2,3,1]
>输出：4
>解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。

>输入：[2,7,9,3,1]
>输出：12
>解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 .

class Solution {
    public int rob(int[] nums) {
        int pre2 = 0, pre1 = 0;
        for (int i = 0; i < nums.length; i++) {
            // 注意这个状态转移，毕竟题目是隔着偷
            int cur = Math.max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

5. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

>输入：nums = [2,3,2]
>输出：3
>解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

>输入：nums = [1,2,3,1]
>输出：4
>解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
    偷窃到的最高金额 = 1 + 3 = 4 。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        if (n == 1) return nums[0];
        // 注意0-n-2 个 1 -n-1
        return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
    }

    private int rob(int[] nums, int first, int last) {
        int pre2 = 0, pre1 = 0;
        for (int i = first; i <= last; i++) {
            int cur = Math.max(pre1, pre2 + nums[i]);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}

6、剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

>输入
>8
>返回值
>18

// 动态规划
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    // 一厘米，没法切，所以从2
    for (int i = 2; i <= n; i++)
    // 切从1cm开始
        for (int j = 1; j < i; j++)
        //  注意这个状态转移
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
    return dp[n];
}

7、礼物的最大值

小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，请设计一个算法使小东拿到价值最高的礼物。

给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。

public int getMost(int[][] values) {
    if (values == null || values.length == 0 || values[0].length == 0)
        return 0;
    int n = values[0].length;
    int[] dp = new int[n];
    for (int[] value : values) {
        dp[0] += value[0];
        for (int i = 1; i < n; i++)
            dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
    }
    return dp[n - 1];
}

8. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

>输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
>输出：7
>解释：因为路径 1→3→1→1→1 的总和最小。

>输入：grid = [[1,2,3],[4,5,6]]
>输出：12

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        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 j = 1; j < n; j++){
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        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];
            }
        }
        return dp[m - 1][n - 1];
        
    }
}

9. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

>输入：m = 3, n = 2
>输出：3
>解释：
>从左上角开始，总共有 3 条路径可以到达右下角。
>1. 向右 -> 向下 -> 向下
>2. 向下 -> 向下 -> 向右
>3. 向下 -> 向右 -> 向下

>输入：m = 7, n = 3
>输出：28

class Solution {
    public int uniquePaths(int m, int n) {
        // 优化过后了
        int[] dp = new int[n];
        // 注意
        Arrays.fill(dp, 1);
        // 注意起始位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 累加
                dp[j] += dp[j - 1];
            }
        }
        return dp[n -1];
    }
}
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = 1;
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];        
    }
}

9.2 不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

>输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
>输出：2
>解释：
>3x3 网格的正中间有一个障碍物。
>从左上角到右下角一共有 2 条不同的路径：
>1. 向右 -> 向右 -> 向下 -> 向下
>2. 向下 -> 向下 -> 向右 -> 向右

>输入：obstacleGrid = [[0,1],[0,0]]
>输出：1

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // 因为if
        int[] dp = new int[n + 1];
        dp[1] = 1; // 注意初始值
        // 起始位置
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 别忘了条件
                if (obstacleGrid[i - 1][j - 1] == 1) 
                    dp[j] = 0;
                else 
                    dp[j] += dp[j - 1];
            }
        }
        return dp[n];
    }
}
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int [][] dp = new int[m+1][n+1];
        // 第一行 和 其他行的区别在于没有来自上边的路径 但是 起点到起点 算一条路径 所以这样初始化
        dp[0][1] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i-1][j-1] == 1) {
                    // 障碍 不可达 路径数量为0
                    dp[i][j] = 0;
                }
                else {
                    // 左 + 上
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 0; i < m; i++){
            for (int j = 0; j < n; j++){
                if (obstacleGrid[i][j] == 1)
                    continue;
                if (i == 0 && j == 0)
                    continue;
                if(i == 0)
                    dp[i][j] = dp[i][j - 1];
                else if (j == 0)
                    dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

9.3 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

>输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
>输出：4

class Solution {
    public int maximalSquare(char[][] matrix) {
        /**
        dp[i][j]表示以第i行第j列为右下角所能构成的最大正方形边长, 则递推式为: 
        dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
        **/
        if (matrix == null ||  matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++){
                if (matrix[i-1][j-1] == '1') {
                    // 左， 上，左上
                    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;
    }
}

10. 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1”（分别为 “K” 和 “A” ）映射为 “KA” 。注意，”06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

>输入：s = "12"
>输出：2
>解释：它可以解码为 "AB"（1 2）或者 "L"（12）。

>输入：s = "226"
>输出：3
>解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1; // 初始值
        // 注意第一个元素是0？
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        // 注意起始位置，
        for (int i = 2; i <= n; i++) {
            // substring 用的很骚
            int one = Integer.valueOf(s.substring(i - 1, i));
            if (one != 0) {
                dp[i] += dp[i - 1];
            }
            // 注意这个判断
            if (s.charAt(i - 2) == '0') continue;
            int two = Integer.valueOf(s.substring(i - 2, i));
            if (two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}

11. 最长上升子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

>输入：nums = [10,9,2,5,3,7,101,18]
>输出：4
>解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

>输入：nums = [0,1,0,3,2,3]
>输出：4

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        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]) {
                    // 注意if
                    dp[i] = Math.max(dp[i], dp[j] + 1); // 关键这里，
                }
            }
        }
        // 找最大
        return Arrays.stream(dp).max().orElse(0);
    }
}

12. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

>输入：text1 = "abcde", text2 = "ace" 
>输出：3  
>解释：最长公共子序列是 "ace"，它的长度为 3。

>输入：text1 = "abc", text2 = "abc"
>输出：3
>解释：最长公共子序列是 "abc"，它的长度为 3。

>输入：text1 = "abc", text2 = "def"
>输出：0
>解释：两个字符串没有公共子序列，返回 0。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(), n2 = text2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n1][n2];
    }
}

15. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

>输入：word1 = "horse", word2 = "ros"
>输出：3
>解释：
>horse -> rorse (将 'h' 替换为 'r')
>rorse -> rose (删除 'r')
>rose -> ros (删除 'e')

>输入：word1 = "intention", word2 = "execution"
>输出：5
>解释：
>intention -> inention (删除 't')
>inention -> enention (将 'i' 替换为 'e')
>enention -> exention (将 'n' 替换为 'x')
>exention -> exection (将 'n' 替换为 'c')
>exection -> execution (插入 'u')

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            dp[0][i] = i;
        }
        // 这dp
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[m][n];
    }

}