温稚

分类

/ 注册

TA的专栏 19篇文章 1人订阅

动态规划题解

17篇文章 550人学习

小米真题题解

0篇文章 0人学习

递归、回溯

2篇文章 369人学习

全部文章（共19篇）

题解 | #环形数组的连续子数组最大和#java小白来自专栏

本题用动态规划求解本题难点在于这个数组是一个环，第一个元素的前一个元素时最后一个元素，不然就是简单的求最大和的连续子序列状态转移方程为：dp[i] = max(dp[i]+ints[i],ints[i]) dp为以第i个元素结尾的子序列的最大和而求最大和，最大和有两种情况，包含首尾以及不包含 ...

2023-11-10

1 370

题解 | #括号生成# 来自专栏

递归第一题（小白向）本题用递归，可以说是dfs求解（附上递归大部分模板）本题括号匹配，要找出最多的，且合法的组合按照步骤找出递归终止条件：当左右两边括号数都达到n时，结束递归不和法的状态：比如说）（）（）（肯定不合法，所以我们选择先放左括号，然后来匹配接下来看行后注释 i...

2023-11-04

1 283

题解 | #N皇后问题# 来自专栏

本题用递归求解（没有回溯）题目要求，在n阶矩阵中，找到所有n个皇后摆放方式，摆放要求不能在同一直线1，同一列，以及同一对角线刚刚开始刷递归以及dfs、回溯的题，在这里总结一下模板，找出终结条件，即使递归结束的条件本题为行数递归到最后一行，代表选择完毕返回剪枝是对于回溯过程中不合题目要求...

2023-11-04

1 369

题解 | #爬楼梯#c++&java&python3 来自专栏

本题用动态规划求解，题解写的时间上，看的人少，请多多点赞支持本题是斐波那契数列的一个变种，主要考察的是大数加减法 java中可以使用BigInteger类实现大数加减 c++我是参考 ‘广州市民林先生’的题解，将斐波那契中的两个数转为字符串，然后一位位加，具体实现看代码，注释很详细 python3...

2023-10-22

2 413

题解 | #风口的猪-中国牛市#Java&&C++（小白向）来自专栏

本题用动态规划求解，题解写的人少，费时间，请多多点赞因为之前做过求单次最大套利多少的题，所以下意识想分情况讨论之前写的文章先说一下一次买入的收益计算方法设dp[n][2] dp[n][0] 为未持有股票时第n天的持有的最大金额 dp[n][1]为第n天持有股票时所持有的最大金额状态...

2023-10-21

2 373

题解 | #最大差值# c++& java& Python3 来自专栏

//本题用动态规划求解 //定义一维数组dp【n】为从开始到以第n个元素为b的最大差值 //理解了dp的定义，记录最大值返回即可 import java.util.*; public class Solution { public int getDis (int[] A, in...

2023-10-13

1 396

题解 | #最长上升子序列(一)# c++ && java 来自专栏

//本题用动态规划解决，建议看我合唱队的那篇题解1，写的很详细，这次就偷个懒了 #include <bits/stdc++.h> using namespace std; int main() { std::ios::sync_with_stdio(false); ...

2023-10-12

1 311

题解 | #拦截导弹# java && c++ 来自专栏

Dilworth定理: 最少的下降序列个数就等于整个序列最长上升子序列的长度 //本题用动态规划求解，合唱队那题很有参考价值，可以参考我上一篇题解 // 本题思路求出最长递减子序列即为一次最多拦截导弹数逆向思维求反方向的最长递增子序列 // if (inits[i] >= ini...

2023-10-12

1 355

题解 | #合唱队形# java && c++ （小白向）来自专栏

//本题用动态规划求解（本人动规初学者以及c++初学者） // 逆向思维求最少出队人数 // 即为求一个 →（箭头）形状的数组中间凸起两边逐渐下降 // 方法：分别从两个方向求出该方向的最长递增序列然后长出最长的箭头状态数组数组长度减去子序列长度 // 定义 dp_lef...

2023-10-12

2 550

题解 | #买卖股票的最好时机(一)# 来自专栏

//本题用动态规划求解 /dp[n][2] 中两列0,1分别表示持有股票和未持有股票 n代表当天最大收益初始值dp[0][0] = 0; //dp状态转移方程为 dp[n][0] = max(dp[n-1][0],dp[n-1][1]+prices[n]) 当天最大收益由两种情况递推而来 //1....

2023-10-11

1 464