疏凉

分类

题解(101)

/ 注册

全部文章（共14篇）

题解 | #把数字翻译成字符串#

动态规划，定义dp数组，初始化为1；当nums[i-1]='0'时，如果nums[i-2]='1'或'2'时，dp[i]=dp[i-2]，否则返回0；当nums[i-1]='1'~'6'时，如果nums[i-2]='1'或'2'时，dp[i]=dp[i+-1]+dp[i-2]，否则返回dp[i]...

C++ 动态规划

2022-04-29

0 309

题解 | #礼物的最大价值#

动态规划，定义dp数组大小为m*n（与grid大小一致），记录当前最大值；初始化，dp[0][0]为grid[0][0]，第一行和第一列为该行和该列的累加值；只能向下或向右移动，确定递推关系：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i]...

C++ 动态规划

2022-04-29

0 362

题解 | #矩形覆盖#

number <= 3，直接返回；定义dp记录前两项的值；递推：当前项=前两项之和；返回最后结果。 class Solution { public: int rectCover(int number) { if (number <= 3) return n...

C++ 动态规划

2022-04-29

0 283

题解 | #连续子数组的最大和(二)#

动态规划，dp数组存储前一最大和、当前最大和；左区间端点更新条件：前一最大和小于0；区间端点更新条件：当前最大和更新，或者当前最大和不变但区间范围增大；遍历完成后，返回区间内的数组元素。 class Solution { public: /** * 代码中的类名、方法名、参...

C++ 数组动态规划

2022-04-29

0 303

题解 | #连续子数组的最大和(二)#

动态规划，定义dp数组记录当前子数组最大和；区间左端点更新条件：前一子数组最大和小于0；区间更新条件：当前子数组最大和更新和当前子数组最大和不变但区间增大；将区间范围内的数组元素放入结果。 class Solution { public: /** * 代码中的类名、方法名、...

C++ 数组动态规划

2022-04-29

0 292

题解 | #兑换零钱(一)#

背包问题，定义dp数组，大小aim+1，初始化为全局最大值aim+1；一开始dp[0]=0；遍历更新dp数组的值；如果能兑换，更新当前目标值的最小兑换数。返回最终结果，不能兑换返回-1，否则返回最终值。 class Solution { public: /** * 最少货...

C++ 数组动态规划

2022-04-21

0 286

题解 | #买卖股票的最好时机(二)#

定义dp数值，大小prices.size() * 2，记录每天买入后和卖出后的持有最大钱数；初始化第一天，买入后持有-prices[0]，卖出后持有0（当天不能卖出）；确定递推关系：当天买入后持有最大钱数=max(前一天买入后持有钱数，前一天卖出后持有钱数-当前买入价格)；当天卖出后持有最大...

C++ 数组动态规划

2022-04-21

0 265

题解 | #跳台阶#

动态规划，定义dp数组，大小为2；初始化前两项；递推关系：当前项为前两项的和，更新dp数组；返回最终结果。 class Solution { public: int jumpFloor(int number) { if (number == 1) return 1; ...

C++ 数组动态规划记忆化搜索

2022-04-13

0 191

题解 | #不同路径的数目(一)#

动态规划，定义dp数组，m行n列；初始化，第一行第一列为1；递推关系：当前位置路径数目=左路径+右路径；返回最终结果。 class Solution { public: /** * * @param m int整型 * @param n int整型 ...

C++ 数组动态规划

2022-04-13

0 297

题解 | #连续子数组的最大和#

遍历数组，进行求和，更新当前连续子数组结果；如果数组和小于0，重新开始累加；遍历完成，返回最终结果。 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { in...

C++ 数组动态规划

2022-04-13

0 227