@[toc]

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

知识点

知识点：递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。

知识点：贪心思想

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

剑指offer

剑指 Offer 62. 圆圈中最后剩下的数字【简单】

和约瑟夫环题目类似，是历史上的一个问题

题目链接：剑指 Offer 62. 圆圈中最后剩下的数字

题目内容：0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

思路：动规。从最后1人往前进行推导。

f(1)最后活下来的是索引0。也就是我们从最后活的那人位置开始不断的进行往前推导
f(2) = (f(1) + ?) % 2， 这个?就是我们题目中说明的m => f(n) = (f(n - 1) + m) % n

1、动规

复杂度分析：时间O(n)、空间O(1)

class Solution {
    public int lastRemaining(int n, int m) {
        //动规
        //f(n)表示在n个人中，值表示能够活下来的索引
        //初始化f(1) = 0
        //转移方程：f(n) = (f(n - 1) + m) % n
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        } 
        return x;
    }
}

---

剑指 Offer 46. 把数字翻译成字符串【中等，与牛客网12题一致】

题目链接：剑指 Offer 46. 把数字翻译成字符串

class Solution {
    public int translateNum(int num) {
        //[0, 25]的符合情况,实际上只需要看[10,25]  dp[i] = dp[i - 1] + dp[i - 2] 
        //>25情况  dp[i] = dp[i - 1]
        String str = "" + num;
        int[] dp = new int[str.length() + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= str.length(); i++) {
            //第一位数是否不为0
                //不为0  ①若二位数符合 dp[i] = dp[i - 1] + dp[i - 2]   ②二位数不符合 dp[i] = dp[i - 1]
                //为0，二位数此时不符合 dp[i] = dp[i - 1]
            //判断当前二位数的数字第一位是否为0
            if (str.charAt(i - 2) != '0') {
                //获取二位数
                String numStr = str.substring(i - 2, i);
                int n = Integer.valueOf(numStr);
                if (n >= 0 && n <= 25) {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }else {
                    dp[i] = dp[i - 1];
                }
            }else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[str.length()];
    }
}

剑指 Offer 14- I. 剪绳子【中等】

学习：剑指 Offer 14- I. 剪绳子的优质题解

题目链接：剑指 Offer 14- I. 剪绳子

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

思路：

1、动态规划

复杂度分析：时间复杂度O(n^2^)，空间复杂度O(n)

class Solution {

    //长度为n的可能被剪成m段，这个m没有限制
    //f(n) = val，n表示长度为n，val表示减m段最大的一个乘积
    //1(1)、2(1x1=1,2)、3(1x2=2,3)、4(1x3=3,2x2=4)、5(1X4=4,2X3=6,5)
    //转移方程：f(n) = Math.max(f(n), f(i)xf(n-i)...,f(i+1)xf(n-i-1))
    //此时我们可以将f(i)...来进行记忆化，也就是f(n)为最大情况
    public int cuttingRope(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++) {
                //计算得到左半部分最长的绳子、右半部分最长，取得积
                int temp = Math.max(dp[j], j) * Math.max(dp[i - j], i - j);
                dp[i] = Math.max(temp, dp[i]);
            }
        }
        return dp[n];
    }
}

2、数学推导

复杂度分析：时间复杂度O(1)、空间复杂度O(1)

class Solution {

    //根据数学公式推出x=3的乘积最大
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        //余数为0时，可计算3的a倍
        if(b == 0) return (int)Math.pow(3, a);
        //余数为1 【3的a次方*1 < a的(a-1)次方*4】，肯定是选择后者
        if(b == 1) return (int)Math.pow(3, a - 1) * 4;
        //余数为2 【3的a次方*2 > a的(a-1)次方*5】，选择前者
        return (int)Math.pow(3, a) * 2;
    }

}

剑指 Offer 14- II. 剪绳子 II【中等】

题目链接：剑指 Offer 14- II. 剪绳子 II

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

与题目I中的区别：①n的边界变大了，此时2<=n<=1000。②最终的结果值需要进行%运算。

思路：

1、数学推导（推导的过程实际上与I中一致，只不过这里的pow运算需要我们自己来进行手动去来进行，过程中需要不断模运算）

复杂度分析：时间复杂度O(n)；空间复杂度O(1)

class Solution {

    //核心：剪绳子成m段，最大的乘积
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        int rem = 1000000007;
        //这一个过程实际上就是得到【pow(3, a-1)】的一个过程，在进行乘积的过程中，不断进行模运算，仅此而已
        //注意：res再进行倍乘的过程里可能会越int的界，所以我们需要将其定义为【long】类型
        long res = 1;
        for (int i = 1; i <= a - 1; i++) {
            res = res * 3 % rem;
        }
        //根据%的结果值来进行列举
        if (b == 0) {
            return (int)(res * 3 % rem);
        }else if (b == 1) {
            return (int)(res * 4 % rem);
        }
        return (int)(res * 6 % rem);
    }
}

我们可以对遍历操作来进行优化：

复杂度分析：时间复杂度O(logn)；空间复杂度O(1)

class Solution {

    private int rem = 1000000007;

    //核心：剪绳子成m段，最大的乘积
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int a = n / 3, b = n % 3;
        //这一个过程实际上就是得到【pow(3, a-1)】的一个过程，在进行乘积的过程中，不断进行模运算，仅此而已
        //注意：res再进行倍乘的过程里可能会越int的界，所以我们需要将其定义为【long】类型
        long res = 1;
        // for (int i = 1; i <= a - 1; i++) {
        //     res = res * 3 % rem;
        // }
        res = pow(3, a - 1);
        //根据%的结果值来进行列举
        if (b == 0) {
            return (int)(res * 3 % rem);
        }else if (b == 1) {
            return (int)(res * 4 % rem);
        }
        return (int)(res * 6 % rem);
    }

    public long pow(int n, int k) {
        if (k == 0) {
            return 1;
        }
        if (k == 1) {
            return n;
        }
        long num = pow(n, k / 2);
        if (k % 2 == 1) {
            return num * num * n % rem;
        }else {
            return num * num % rem;
        }
    }
}

剑指 Offer 63. 股票的最大利润【中等，等同牛客网的第6题】

题目链接：剑指 Offer 63. 股票的最大利润

题目内容：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

思路：

1、贪心：维护一个最大收益以及一个最低价买入

复杂度分析：时间复杂度O(n)、空间复杂度O(1)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE, minPrice = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max, minPrice + prices[i]);
            minPrice = Math.max(minPrice, -prices[i]);
        }
        return max < 0 ? 0 : max;
    }
}

2、动态规划：也可以解决多次买入卖出问题

复杂度分析：时间复杂度O(n)、空间复杂度O(n)

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        //状态定义：dp[i][2]，dp[i][0]表示的是卖出股票的最大收益，dp[i][1]表示买股票的最低点
        //初始状态：dp[0][0],dp[0][1] = -prices[0]
        //转移方程：dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0])，dp[i][1] = Math.min(dp[i - 1][1], -prices[i])
        //返回：dp[prices.length - 1][0]
        int[][] dp = new int[prices.length][2];
        dp[0][0] = dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        //若是所有的方案都亏钱，那么就不进行方案操作直接返回0
        return dp[prices.length - 1][0] < 0 ? 0 : dp[prices.length - 1][0];
    }
}

---

剑指 Offer 60. n个骰子的点【中等】

题目链接：剑指 Offer 60. n个骰子的点数

题目内容：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

思路：

1、递归【在leetcode上超时，n=9时】

复杂度分析：时间复杂度 O(6^n^)；空间复杂度O(1)

class Solution {
    public double[] dicesProbability(int n) {
        //暴力求法,可能投到的点数
        List<Integer> counts = new ArrayList<>();
        int sum = 0;//总次数
        for (int i = n; i <= n * 6; i++) {
            int num = dfs(i, n);
            sum += num;
            counts.add(num);
        }
        //定义概率数组
        double[] dp = new double[5 * n + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = counts.get(i) * 1.0 / sum * 1.0;
        }
        return dp;
    }

    //sum表示投得的点数
    //n表示当投筛子的次数
    public int dfs(int sum, int n) {
        //若是sum为小于0
        if (sum < 0 || n < 0) {
            return 0;
        }
        //若是最终扣减的值为0且投掷的次数也为0表示是一种方案
        if (sum == 0 && n == 0) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= 6; i++) {
            res += dfs(sum - i, n - 1);
        }
        return res;
    }
}

2、动态规划【推荐】

复杂度分析：时间复杂度O(n^2^)；空间复杂度O(n)

class Solution {
    public double[] dicesProbability(int n) {
        //状态定义：dp[i][j]=val，表示i个筛子投到点数j的概率
        //状态转移方程：dp[i][j] = dp[i][j] + dp[i - 1][j - 1] / 6.0
        double[] dp = new double[6];//初始化6个，因为1个筛子能够投到6
        Arrays.fill(dp, 1.0 / 6.0);
        //筛子的数量作为遍历的次数
        for (int i = 2; i <= n; i++) {
            //初始化对应新的筛子数可能投中的点数
            double[] temp = new double[5 * i + 1];
            //前i - 1个筛子投之后数的大小
            for (int j = 0; j < dp.length; j++) {
                //最大是6个点
                for (int k = 0; k < 6; k++) {
                    temp[j + k] += dp[j] / 6.0;//新的一轮的话，就需要x6倍，例如1个筛子可以投1-6，也就是6次几率，两个筛子就是6x6=36次
                }
            }
            dp = temp;
        }
        return dp;
    }
}

---

剑指 Offer 47. 礼物的最大价值【中等】

题目链接：剑指 Offer 47. 礼物的最大价值

题目内容：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

思路：

1、动态规划

复杂度分析：时间复杂度O(n^2^)，空间O(1)

class Solution {
    public int maxValue(int[][] grid) {
        //状态定义：dp[i][j]=val，移动到第第i，j位置时可取得的最大价值
        //转移方程：dp[i][j] = Math.max(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j])（i > 0, j > 0）
        //初始化：i=0，j=0
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1;j < m; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
            }
        }
        return dp[n - 1][m - 1];
    }
}

---

剑指 Offer 43. 1～n 整数中 1 出现的次数【困难】

题目链接：剑指 Offer 43. 1～n 整数中 1 出现的次数

题目内容：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

0-9    【1】
    10-99  19
      10 11-19 21 31 41 - 91  19个
0-99   【20】
0-999  【300】
结论：从[0, pow(10, i) - 1]的个数为i*pow(10, i - 1)，i指的是位数。

假设n，若是n > (pow(10, i) - 1)，那么来进行累加，n - (pow(10, i) - 1)，循环累减，直到 n <= (pow(10, i) - 1)

举例：n=234
dp[i] = val，i表示的是位数，val即为值
dp[0] = 0  dp[1] = 1  dp[2] = 20 dp[3]=300
234根据区间来拆分为：[0,99]、[100,199]、[200,234]
	[0,99]、[100,199]：dp[2] * (234/100) + pow(10,2) = 40 + 100 = 【140】
	[200, 234]：中1的个数之和等于[0, 34]之间，
		[0, 9], [10, 19], [20, 29], [30, 34]进行拆分：
			[0, 9], [10, 19], [20, 29]：(34/10) * dp[1] + pow(10, 1) = 3 + 10 = 【13】
			[30, 34]: (4/1)*dp[0] + pow(10, 0) = 【1】
最终合并起来就是：140+13+1=154
	[0,99]、[100,199]           =>  (234/100) * dp[2] + pow(10,2) = 40 + 100 = 【140】 
	[0, 9], [10, 19], [20, 29]  =>  (34/10) * dp[1] + pow(10, 1) = 3 + 10 = 【13】
	[30, 34]                    =>  (4/1)*dp[0] + pow(10, 0) = 【1】

思路1：找规律

复杂度分析：时间复杂度O(logn)；空间复杂度O(1)

class Solution {

    //234（所有例子都是ans += b * dp[i] + temp）
    //i = 0  a = 0   b = 4   temp = 1   ans+=4 * dp[0] + 1= 4 * 0 + 1 = 1   实际上计算的是[0,4]
    //i = 1  a = 4   b = 3   temp = 10  ans+=3 * dp[1] + 10 = 3 + 10 = 14   实际上计算机的是[0, 34] => [0,4]、[10, 19]、[20,29]、[30,34]的个位数，对于10-19的十位数有10个
    //                                                                                              3个个位上的，10个十位上的数以及之前的个人数
    //i = 2  a = 3   b = 2   temp = 100  ans+=2 * dp[2] + 100 = 40 + 100 = 154

        //214
    //到b==1时（该例子是ans += a + dp[i] + 1;）
    //i = 1 a = 4  b = 1  temp = 10  ans+=4 + dp[1] + 1
    //                                4+1=>[10,14]的十位数、dp[1]=1表示的是[10,14]的个位数
    public int countDigitOne(int n) {
        //dp准备10位数的所有情况
        int[] dp = new int[10];
        dp[0] = 0;
        dp[1] = 1;
        //开始提前进行计算
        //0 1 20 200+200/2
        for (int i = 2; i < 10; i++) {
            //等同于i * pow(10, i - 1)
            dp[i] = dp[i - 1] * 10;
            dp[i] = dp[i] + dp[i] / (i - 1);
        }
        //ans表示结果集、i表示位数
        int ans = 0, i = 0;
        long temp = 1;//表示各段的进位数
        while (temp <= n) {
            //a表示当前temp的取模结果，b表示各个temp的对应的位数
            int a = (int)(n % temp), b = (int)((n % (temp * 10)) / temp);
            //根据b的值来进行推断
            if (b > 1) {
                ans += b * dp[i] + temp;
            }else if (b == 1) {
                ans += a + dp[i] + 1;
            }
            temp *= 10;
            i++;
        }
        return ans;
    }
}

牛客网

跳台阶【简单】

题目链接： 跳台阶

题目内容：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路1：迭代法（动态规划）。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
    //来自leetcode：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/submissions/
    public int numWays(int n) {
        if (n <= 1) {
            return 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]) % 1000000007;
        }
        return dp[n];
    }
}

优化动态规划：通过使用数组的方法，会有很多空间会被浪费掉，其实使用三个变量就ok了，空间复杂度大大优化。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

public class Solution {
    //迭代法
    public int jumpFloor(int target) {
        if (target <= 1) {
            return 1;
        }
        int res = 0;
        int a = 1;
        int b = 1;
        for (int i = 2;i <= target; i++) {
            res = a + b;
            a = b;
            b = res;
        }
        return res;
    }
}

思路2：递归

复杂度分析：

• 时间复杂度：O(2^n^)
• 空间复杂度：O(1)

public class Solution {
    
    //迭代法
    public int jumpFloor(int target) {
        if (target == 0 || target == 1) {
            return 1;
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

优化：上述递归会出现大量重复的计算，我们可以使用一个dp数组来另其具备记忆化。

public class Solution {
    
    //记忆化数组
    private int dp[] = new int[40];
    
    //迭代法
    public int jumpFloor(int target) {
        if (target == 0 || target == 1) {
            return 1;
        }
        //来进行记忆化判断，若是之前计算过，那么就无需再重复计算
        if (dp[target] != 0) {
            return dp[target];
        }
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

最小花费爬楼梯【简单】

题目链接：最小花费爬楼梯

题目内容：给定一个整数数组 cost cost ，其中 cost[i]*cos**t*[i] 是从楼梯第i *i* 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

思路：采用动态规划。使用dp数组来保存每个格子最小花费，推出递归公式为：dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        //设置dp数组：下标表示第几层，值为最小花费
        //dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i <= cost.length;i++) {
            dp[i] = Math.min(dp[i - 1] +  cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

不同路径的数目(一)【简单】

题目链接：不同路径的数目(一)

题目内容：一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

思考区

约束条件：

1、机器人每次只能往右或者往下走。

2、机器人不能越界。

解题

思路1：动态规划

定义状态方程：

dp[i][j] = val  i表示行，j表示列，val表示方案数量
当i>1 && j>1  dp[i][j] = dp[i][j-1] + dp[i-1][j]
当i=0时，dp[i][j] = dp[i][j-1]
当j=0时，dp[i][j] = dp[i-1][j]

复杂度分析：

• 时间复杂度：O(n*m)
• 空间复杂度：O(n*m)

代码：

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
       //定义dp数组
        int[][] dp= new int[m][n];
        
        for (int i = 0;i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

思路2：递归

import java.util.*;


public class Solution {
    
    
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        if (m == 1 || n == 1) {
            return 1; 
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

上面的时间复杂度是2^n^，如何优化呢？进行记忆化状态方程

class Solution {
    private int[][] dp;

    public int uniquePaths(int m, int n) {
        if (dp == null) {
            dp = new int[m + 1][n + 1];
        }
        if (m == 1 || n == 1) {
            return 1;
        }
        if (dp[m][n] == 0) {
            dp[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
        }
        return dp[m][n];
    }
}

此时无论是时间还是空间复杂度与思路1一致。

连续子数组的最大和【简单】

题目链接：连续子数组的最大和

题目内容：输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

思路

关键词：连续、最大。

dp[i] = val：i表示当前数组下标索引，val表示截止到目前连续的最大和

列出dp方程组：dp[i] = Math.max(array[i], dp[i-1] + array[i]);

解题

思路1：动态规划

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = dp[0];
         //dp[i] = Math.max(array[i], dp[i-1] + array[i]);
        //下标：到index时最大的值位置  值；最大连续和
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(array[i], dp[i-1] + array[i]);
            if(max < dp[i]) {
                max = dp[i];
            }
        }
        return max;
    }
}

---

买卖股票的最好时机(一)【简单】

题目链接：买卖股票的最好时机(一)

题目内容：假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益。

思路1：暴力法（超时）

复杂度分析：

• 时间复杂度：O(n^2^)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length;i++) {
            for (int j = i + 1;j < prices.length; j++){
                ans = Math.max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }
}

思路2：贪心算法，维护一个最小值来进行不断比较。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int min = Integer.MAX_VALUE;
        int ans = 0;
        for (int i = 0; i < prices.length;i++) {
            //维护一个最小值
            min = Math.min(prices[i], min);
            //不断的比对（截止今天之前的最大收益，当前价格-最小值）
            ans = Math.max(ans, prices[i] - min);
        }
        return ans;
    }
}

---

买卖股票的最好时机(二)【中等】

与第6题的区别在于：这里可以多次买卖股票，让你求得一个最大收益。

区别在于可以多次买入卖出。 但是对于每天还是有到此为止的最大收益和是否持股两个状态，因此我们照样可以用动态规划。

思路：动态规划。

复杂度分析：

• 时间复杂度：
• 空间复杂度：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        //dp动态规划。0下标:表示未持有时最大收益。1下标：表示持有时的一个最大收益。
        //dp[i][0] = Math.max(dp[i - 1][0], (dp[i - 1][1] + prices[i]))
        //dp[i][1] = Math.max(dp[i - 1][1], (dp[i - 1][0] - prices[i]))
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -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][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

---

买卖股票的最好时机(三)【困难】

区别：最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票.

设置一个五维数组，然后分别来进行记录。

思路：动态规划。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        //dp[i][j] (j在0-4中)， i表示第几天。j的0-4分别表示：未买入、第一次买入、第二次卖出、第二次买入、第二次卖出
        //状态方程定义与初始化
        int n = prices.length;
        int[][] dp = new int[n][5];
        //第一天
        Arrays.fill(dp[0], -10000);//最大股票10000元
        for (int i = 0; i < n; i++) {
            dp[i][0] = 0;
        }
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        //可能两次交易收益最后或者一次交易最多
        return Math.max(dp[n - 1][4], Math.max(0, dp[n - 1][2]));
    }
}

---

兑换零钱【中等】

学习视频：Leetcode 322 零钱兑换 【动态规划解法】（讲的不太清楚）、动态规划19：例题：零钱兑换问题的分析（推荐）

题目地址：兑换零钱(一)

题目描述：给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1.

思路1：采用动态规划，列出状态方程组。

1、dp数组下标[1,amount]表示金额数，dp的值表示对应金额的最小硬币数。

2、dp[i] = min(dp[i], dp[i-arr[j] + 1])。

3、初始化每个数组值为最大硬币数+1。

4、迭代遍历所有金额情况及对应面值情况。

5、设置符合的条件（coins[j] <= i，面额要小于对应总额）来进行状态方程推导。

class Solution {
    //dp数组下标[1,amount]表示金额数，dp的值表示对应金额的最小硬币数
    //dp[i] = min(dp[i], dp[i-arr[j] + 1])
    public int coinChange(int[] coins, int amount) {
        //边界条件
        if (amount < 1) {
            return 0;
        }
        //定义dp数组,数量为金额数
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);//硬币数的范围肯定是0 - amount，所以这里的话是最大硬币数
        //当目标金额为0时，0个硬币数
        dp[0] = 0;
        //迭代所有金额
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        //最后返回对应的一个dp[amount]即可
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

最长系列【中等】

最长公共子序列(二)【中等】

题目链接：最长公共子序列(二)

题目内容：给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回"-1"。目前给出的数据，仅仅会存在一个最长的公共子序列

思路：dp+递归。①nxn遍历，来进行计算dp中每个格子的可连接

示例：把思路理清楚了就ok。

"1A2C3D4B56", "B1D23A456A"
结果：123456

下图中每个格子的左边是dp的值，右边红色的是方向数组b的值。左下角包含有思路解决：

复杂度分析：

• 空间复杂度：O(n^2^)
• 时间复杂度：O(n^2^)

import java.util.*;


public class Solution {
    
    private String x;
    private String y;
    
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        this.x = s1;
        this.y = s2;
        char[] sArr1 = s1.toCharArray();
        char[] sArr2 = s2.toCharArray();
        int[][] dp = new int[sArr1.length + 1][sArr2.length + 1];
        int[][] d = new int[sArr1.length + 1][sArr2.length + 1];
        for (int i = 1; i <= sArr1.length; i++) {
            for (int j = 1; j <= sArr2.length; j++) {
                //比较两个字符
                if (sArr1[i - 1] == sArr2[j - 1]) {
                    //若是相同
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    d[i][j] = 1;
                }else {
                    if (dp[i - 1][j] > dp[i][j - 1]) {
                        dp[i][j] = dp[i - 1][j];
                        d[i][j] = 2;
                    }else {
                        dp[i][j] = dp[i][j - 1];
                        d[i][j] = 3;
                    }
                }
            }
        }
        String ans = ans(s1.length(), s2.length(), d);
        if (ans.isEmpty()) {
            return "-1";
        }
        return ans;
    }
    
    //递归获取最长子序列
    public String ans(int i, int j, int[][] d) {
        String res = "";
        if (i == 0 || j == 0) {
            return res;
        }
        if (d[i][j] == 1) {
            res += ans(i - 1,j - 1, d);
            res += x.charAt(i - 1);
        }else if (d[i][j] == 2) {
            res += ans(i - 1,j, d);
        }else {
            res += ans(i, j - 1, d);
        }
        return res;
    } 
}