整数拆分
题目描述
题目链接：343. 整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例1：
123输入: n = 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。
示例2：
123输入: n = 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示：
2 <= n <= 58
我的题解方法一：动态规划思路考虑一个整数拆或者不拆，则递推公式为：
1dp[i] = Math.max(dp[i - j] * j, (i - j) * j)
代码123456789101112class Solution { public int integerBreak(int n) { int[] dp = new int[n]; dp[0] = 1; for (int i = 1; i < dp.length; i++) { ...
不同路径 II
题目描述
题目链接：63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例1：
123456输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]输出：2解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1. 向右 -> 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右 -> 向右
示例2：
12输入：obstacleGrid = [[0,1],[0,0]]输出：1
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1
...
不同路径
题目描述
题目链接：62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
12输入：m = 3, n = 7输出：28
示例1：
1234567输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下
示例2：
12输入：m = 7, n = 3输出：28
示例3：
12输入：m = 3, n = 3输出：6
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10(9)
我的题解方法一：动态规划思路假设当前位置为(i, j)，那么有两种路径可以到达当前位置，即(i-1, j)和(i, j-1)，因此到达当前位置的路径数可由左边和上边的路径推出，因此递推公式为：
1dp[i][j ...
使用最小花费爬楼梯
题目描述
题目链接：746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例1：
12345输入：cost = [10,15,20]输出：15解释：你将从下标为 1 的台阶开始。- 支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。
示例2：
12345678910输入：cost = [1,100,1,1,1,100,1,1,100,1]输出：6解释：你将从下标为 0 的台阶开始。- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。- 支付 1 ，向上爬一个台阶，到达楼梯顶部。总花费为 6 。
提示：
2 <= co ...
爬楼梯
题目描述
题目链接：70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例1：
12345输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶
示例2：
123456输入：n = 3输出：3解释：有三种方法可以爬到楼顶。1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶
提示：
1 <= n <= 45
我的题解方法一：动态规划思路当爬到第n阶楼梯时，有两种方法可以到达：
从n-1阶楼梯爬1阶到第n阶
从n-2阶楼梯爬2阶到第n阶
因此动态规划公式为：dp[n] = dp[n-1] + dp[n-2]
因为当前状态只依赖前两个状态，因此，可以使用变量优化
代码1234567891011121314class Solution { public int climbStairs(int n) { if (n < 3) { ...
斐波那契数
题目描述
题目链接：509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
12F(0) = 0，F(1) = 1F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。
示例1：
123输入：n = 2输出：1解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例2：
123输入：n = 3输出：2解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例3：
123输入：n = 4输出：3解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
0 <= n <= 30
我的题解方法一：动态规划思路一个简单的状态转移
代码1234567891011121314class Solution { public int fib(int n) { if (n == 0 || n == 1) { ...
子集
题目描述
题目链接：78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例1：
12输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例2：
12输入：nums = [0]输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
我的题解方法一：回溯思路当前元素选或者不选
代码123456789101112131415161718192021class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); ...
字符串相乘
题目描述
题目链接：43. 字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例1：
12输入: num1 = "2", num2 = "3"输出: "6"
示例2：
12输入: num1 = "123", num2 = "456"输出: "56088"
提示：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
我的题解方法一：模拟乘法思路模拟乘法计算过程，使用数组记录中间值。
代码1234567891011121314151617181920212223242526272829class Solution { pub ...
括号生成
题目描述
题目链接：22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例1：
12输入：n = 3输出：["((()))","(()())","(())()","()(())","()()()"]
示例2：
12输入：n = 1输出：["()"]
提示：
1 <= n <= 8
我的题解方法一：回溯+剪枝思路回溯法枚举所有情况，其中根据条件进行剪枝：当已加入的右括号大于左括号，这时不能够构成一个有效的括号
代码12345678910111213141516171819202122232425262728class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>( ...
滑动窗口最大值
题目描述
题目链接：239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例1：
1234567891011输入：nums = [1,3,-1,-3,5,3,6,7], k = 3输出：[3,3,5,5,6,7]解释：滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
示例2：
12输入：nums = [1], k = 1输出：[1]
提示：
1 <= ...