解题思路 要求最大收益，我们需要找到最低的买入价格和在该买入价格之后的最高卖出价格。可以遍历一次数组：  用一个变量记录当前遍历过的最低价格 用另一个变量记录当前能获得的最大利润 对于每个价格，尝试更新最低价格，并计算当前价格卖出能获得的利润  代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int maxProfit(vector<int>& prices) { if(prices.empty()) return 0; int...

解题思路 这是一个求最少跳跃次数的问题，可以通过贪心算法来解决：  维护当前能到达的最远位置  维护当前这一跳能到达的边界  维护最少跳跃次数  遍历数组时：  更新当前能到达的最远位置 当到达当前跳跃的边界时，更新边界并增加跳跃次数   如果最终不能到达终点，返回   代码   cpp   java   python   #include <iostream> #include <vector> using namespace std; int minJumps(vector<int>& nums) { int n = nums.size(); i...

解题思路  使用  数组记录到达每个位置能获得的最大积分 对于每个位置 ，遍历其能跳到的所有位置  状态转移方程： 需要先判断位置是否可达，使用一个布尔数组记录可达性 最后检查终点是否可达，如果可达则返回 ，否则返回   代码   cpp   java   python   #include <iostream> #include <vector> using namespace std; int maxScore(vector<int>& nums) { int n = nums.size(); if (n == 0) return -1; if ...

解题思路 这是一个判断能否跳到数组末尾的问题，可以通过贪心算法来解决：  维护一个变量 ，表示当前能够到达的最远位置 遍历数组，对于每个位置 ：  如果  超过了 ，说明无法到达该位置，返回  更新    如果能遍历完整个数组，说明可以到达末尾  代码   cpp   java   python   #include <iostream> #include <vector> using namespace std; bool canJump(vector<int>& nums) { int n = nums.size(); int maxReach ...

解题思路 这是一个求不相邻数字最大和的问题，可以通过动态规划来解决：  定义  表示前  个数中能选择的不相邻数字的最大和 对于第  个数，有两种选择：  选择第  个数： 不选择第  个数：   状态转移方程： 初始条件：       代码   cpp   java   python   #include <iostream> #include <vector> using namespace std; long long maxSum(vector<int>& nums) { int n = nums.size(); if (n == 0) re...

解题思路 这是一个求最长回文子序列的问题，可以通过动态规划来解决：  定义  表示字符串  在区间  内的最长回文子序列长度 状态转移方程：  当  时： 当  时：   初始条件：  当  时，（单个字符是回文）   最终答案是   代码   cpp   java   python   #include <iostream> #include <vector> #include <string> using namespace std; int longestPalindromeSubseq(string s) { int n = s.length(); ...

解题思路 这是一个求矩阵中最长递减路径的问题，可以通过记忆化搜索来解决：  对于矩阵中的每个点，都可以作为起点 从每个点出发，可以向上下左右四个方向移动，但要求移动到的点的高度严格小于当前点 使用记忆化数组来存储每个点作为起点的最长路径长度，避免重复计算 最终答案是所有点作为起点的最长路径中的最大值  代码   cpp   java   python   #include <iostream> #include <vector> using namespace std; int dx[4] = {-1, 1, 0, 0}; // 方向数组：上下左右 int dy[4] ...

解题思路 这是一个求最长山峰序列的问题，可以通过动态规划来解决：  对于每个位置 ，分别求出以  为山峰的最长上升子序列长度和最长下降子序列长度 使用两个  数组：   表示从左到  的最长上升子序列长度  表示从  到右的最长下降子序列长度   遍历所有位置，找出最长的山峰序列 用总人数减去最长山峰序列的长度即为需要出列的人数  代码   cpp   java   python   #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n;...

解题思路 这道题包含两个子问题：  最长非递增子序列（第一个答案）  使用动态规划， 表示以第  个数结尾的最长非递增子序列长度   最少需要的拦截系统数量（第二个答案）  贪心算法，每次选择可以接的最大数 类似于分配会议室的思路    代码   c++   java   python   #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> he...

解题思路 这是一个典型的动态规划问题：   表示到达位置  的最小路径和 每个位置只能从上方或左方到达 状态转移方程： 需要特别处理第一行和第一列，因为它们只能从一个方向到达  代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> matrix(n, vector<int>(m))...

解题思路 这是一个动态规划问题：  每一步可以选择跨一步或两步  表示到达第  个台阶的最小花费  最后需要比较到达最后一个台阶和倒数第二个台阶的花费  代码   c++   java   python   #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> cost(n); for(int i = 0; i < n; i++) { cin >> cost[i]; } vector...

解题思路 这是一道动态规划的题目，我们可以这样分析：  当青蛙处在第  级台阶时，它可以从前面的任意一级台阶跳过来 因此  同理  两式相减得： 最终可以推导出   代码   c++   java   python   #include <iostream> using namespace std; int main() { int n; cin >> n; cout << (1 << (n-1)) << endl; return 0; }   import java.util.Scanner; public class Main {...

解题思路 斐波那契数列的计算有多种方法，这里使用最简单的迭代方法：  特判  或  的情况，直接返回  使用两个变量  和  分别记录前两个数 迭代  次，每次计算下一个斐波那契数 最终  即为所求的第  个斐波那契数  代码   c++   java   python   #include <iostream> using namespace std; int main() { int n; cin >> n; if(n <= 2) { cout << 1 << endl; return 0; } int a = 1, b = 1; fo...

解题思路  定义  表示  的前  个字符和  的前  个字符的最长公共子序列长度 如果 ，则  如果 ，则  最终答案为   代码   c++   java   python   #include <iostream> #include <vector> #include <string> using namespace std; int main() { int n, m; cin >> n >> m; string s1, s2; cin >> s1 >> s2; vector<vector<...