考察的知识点：动态规划；解答方法分析：定义变量m和n，分别表示输入二维数组的行数和列数。创建一个三维数组dp，dp[i][j][k]表示以第i行第列为右下角的正方形的最大边长，k取值为0、1、2，分表示以该点为右下角的正方形的最大边长计算方式（0代表以水平向延伸，1代表以垂直方向延伸，2代表以对角线方向延伸）。初始化ans为-1，用于记录最大的正方形边长的平方。遍历二维数组，外层循环遍历行，内层循环遍历列。对于每个点，如果为字符’C’，则进行如下操作：更新dp[i][j][0]为dp[i][j-1][0] + 1，表示以当前点为右下角的正方形在水平方向上的最大边长。更新dp[i][j][1]为...

考察的知识点：动态规划；解答方法分析：计算所有奶牛的总体重量 totalWeight，并检查它是否能够被3整除。如果不能被3整除，那么无法将奶牛分成三组，直接返回 false。确定每组的目标体重 targetWeight，即 totalWeight / 3。定义一个长度为3的数组 groupSums，用于记录每组的体重和。初始时，所有组的和都为0。调用回溯函数 backtrack(weights, 0, groupSums, targetWeight)，尝试将奶牛分到三组中的某一组中。在回溯函数中，首先查是否所有奶牛已经分完，即 index == weights.length。如果是，则检查每...

考察的知识点：动态规划；解答方法分析：定义一个二维数组dp，dp[i][j]表示在前i个元素中是否存在一个子集，它们的和恰好为j。初始时，dp[0][0]为true。逐个考虑每个元素weights[i]，对于第i个元素，有两种情况：当weights[i]大于当前的目标值j时，dp[i][j]的值与dp[i-1][j]相同，表示前i-1个元素已经可以组成j的和，第i个元素不用考虑，所以dp[i][j] = dp[i-1][j]。当weights[i]小于等于当前的目标值j时，dp[i][j]的值等于dp[i-1][j]或dp[i-1][j-weights[i]]，即dp[i][j] = dp[i...

考察的知识点：二维数组；解答方法分析：获取矩阵的大小n，即矩阵的行数或列数。创建一个与原矩阵相同大小的新矩阵rotatedMatrix，用于存储旋转后的矩阵。使用两层循环遍历原矩阵中的每个元素。将原矩阵中第i行第j列的元素，赋值给新矩阵中第i列倒数第j+1行的位置。即将原矩阵中的每一列逆序赋值给新矩阵中的每一行。返回旋转后的矩阵rotatedMatrix。所用编程语言：C++；完整编程代码：↓ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix int整型vector&l...

考察的知识点：二分查找；解答方法分析：将平方根的可能范围设置为[0, x]；循环迭代直到找到一个精度足够的平方根值。所用编程语言：C++；完整编程代码：↓ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param x int整型 * @return string字符串 */ string mySqrt(int x) { double left = 0, right = x; while (right - left > 1e-6) { double mid = (left + right...

考察的知识点：动态规划；解答方法分析：初始化一个大小为 n+3 的动态规划数组 dp，其中 n 是给定有序列表 height 的长度。使用这个数组来存储每个位置对应的最小能量消耗。从列表的末尾开始遍历，即从位置 n-1 开始倒序遍历到位置 0。对于每个位置 i，计算当前位置 i 的最小能量消耗：height[i] + min(dp[i + 1], dp[i + 2], dp[i + 3])。其中 dp[i + 1]、dp[i + 2] 和 dp[i + 3] 分别表示从位置 i+1、i+2 和 i+3 继续跳跃所需要的最小能量消耗。返回三个起点（位置 0、位置 1 和位置 2）中的最小能量消耗...

考察的知识点：动态规划；解答方法分析：函数uniquePathsWithCows首先判断输入的矩阵cows是否为空或者其中的行或列是否为空，如果是，则返回0。调用dfs函数进行DFS搜索，初始时，行和列的引都是0，hasCow参数为false。dfs函数首先获取输入矩阵的维度m和n。然后，它查当前坐标（row，col）是否超出矩阵范围或者是否遇到了障碍物，如果是，则返回0。如果当前位置上有一头牛，则将hasCow参数标记为true。检查当前坐标是否为终点，且hasCow为true，如果是，则返回1，表示找到了一条符合条件的路径。递归调用dfs函数，分别向下和向右移动，并将hasCow参数传递下...

考察的知识点：动态规划；解答方法分析：定义一个二维数组dp，其中dp[i][j]表示从起点到达位置(i, j)的不同路径数目。初始化dp数组。由于只能向下或向右移动，所以第一行和第一列的位置只能从左方或上方到达，因此，如果某个位置有障碍物或者其左方或上方有障碍物，则该位置的路径数为0，否则为1。使用动态规划的思想来递推整个dp数组。对于位置(i, j)，从左方和上方到达，到达位置(i, j)的路径数等于到达其左方位置(i-1, j)的路径数加上到达其上方位置(i, j-1)的路径数，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。但是如果位置(i, j)有障碍物，则路径...

考察的知识点：动态规划；解答方法分析：定义一个二维数组 arr，大小与输入的三角形数组 cows 相同，用于存储达每个位置的最小总权重。初始化 arr[0][0] 为 cows[0][0]，即三角形的顶部元素。针对三角形的第一列（即 cows[i][0]），从上往下计算到达每个位置的最小总权重，存储在数组 arr[i][0] 中。计算方法为 arr[i][0] = arr[i-1][0] + cows[i][0]。针对三角形的其他位置，例如 cows[i][j]，从上往下计算到达每个位置的最小总权重，存储在数组 arr[i][j] 中。计算方法为 arr[i][j] = min(arr[i-1...

考察的知识点：动态规划；解答方法分析：创建一个长度为 totalWeight + 1 的数组 dp，并将所有元素初始化为无穷大。设置初始条件 dp[0] = 0，表示不需要吃货就能达到重量为 0 的状态。从重量为 1 开始遍历到 totalWeight，对于每个重量 i，遍历待选择的食物重量。如果当前的食物重量 weights[j] 小于等于 i，表示可以选择这个食物，并判断选择这个食物后的状态是否更优（即 dp[i - weights[j]] + 1）。如果更优，就更新 dp[i] 的值为最小的吃货次数。这样在遍历完所有待选择的食物后，dp[totalWeight] 就表示达到目标重量 to...

考察的知识点：动态规划；解答方法分析：创建一个动态规划数组dp，dp[i]表示从0到i的子串能否被拆分成词汇表中的单词。使用一个双重循环来遍历字符串s的所有子串。外层循环遍历每个子串的末尾位置，内层循环遍历每个子串的起始位置。在内层循环中，判断当前子串是否在词汇表中。如果当前子串在词汇表中，更新dp数组，将dp[i]置为true。返回dp数组的最后一个元素，即dp[s.size()-1]，表示整个字符串s能否被拆分成词汇表中的单词。所用编程语言：C++；完整编程代码：↓ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

考察的知识点：动态规划；解答方法分析：定义一个二维数组dp，其中dp[i][j]表示将s1的前i个字符变更为s2的前j个字符所需的最少操作次数。初始化dp数组的第一行和第一列，即dp[0][j]和dp[i][0]，对应于将空字符串变更为s2的前j个字符和将s1的前i个字符变更为空字符串，所需的操作次数就是对应的字符数量。从s1的第一个字符开始遍历到末尾，对于每个字符s1[i]，再从s2的第一个字符遍历到末尾，对于每个字符s2[j]，分为以下几种情况：如果s1[i]等于s2[j]，即当前字符相等，那么不需要进行任何操作，dp[i][j]等于dp[i-1][j-1]，即前一个字符的操作次数。如果s...

考察的知识点：动态规划；解答方法分析：定义一个二维数组dp，dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前(i+j)个字符。当s1和s2都为空字符串时，s3也必须为空字符串，因此dp[0][0] = true。当s1为空字符串时，s3[i]必须等于s2[j]，dp[0][j] = (s3[j-1] == s2[j-1]) && dp[0][j-1]，即前j个字符能否交错组成s2的前j个字符。同理，当s2为空字符串时，dp[i][0] = (s3[i-1] == s1[i-1]) && dp[i-1][0]。当s1的第i个字符和s3的第...

考察的知识点：动态规划；解答方法分析：定义一个二维数组dp，其中dp[i][j]表示从字符串s的第i个字符到第j个字符之间的最长回文子序列的长度。对于长度为1的子序列，dp[i][i]的值都为1。根据子序列的长度逐步增加，对于长度为len的子序列，遍历所有起始位置i，计算dp[i][i+len-1]的值。如果s[i]等于s[i+len-1]，则dp[i][i+len-1]的值等于dp[i+1][i+len-2]的值上2，即字符串s的第i+1个字符到第i+len-2个字符之间的最长回文子序列的长度加上2如果s[i]不等于s[i+len-1]，则dp[i][i+len-1]的值等于dp[i+1][...