昨天电脑在跑东西,卡的不行,用ipad写的题,没在csdn上写
413. 等差数列划分
1、有些思路了,写下看看。
class Solution:def numberOfArithmeticSlices(self, nums: List[int]) -> int:n len(nums)dp[0]*nfor i in range(2,n…
264. 丑数 II
1、大致有思路了,用3个index记录。 2、通过了dp中记录的是d第n个丑数,不能压缩,因为可能会用到。
class Solution:def nthUglyNumber(self, n: int) -> int:index_2,index_3,index_50,0,0dp [1][0]*(n-1)for i in range(1,…
790浮点二分
ee挑战模式成功了,但没有截图
795前缀和 796 二维前缀和
一测试就暴露出问题了——预处理的公式要过脑子呀,不要在没印在脑子里的时候就瞎写哦。
n,m,q map(int, input().split())
a [[0]*(m1) for _ in range(n1)]
for i in range(1,…
300. 最长递增子序列
1、自己的想法有漏洞—— def lengthOfLIS(self, nums: List[int]) -> int:n len(nums)if n1:return 1max_len1dp [[0]*n for _ in range(n)]for i in range(n-1,-1,-1):dp[i][i]itmp_len 1for j in range(i1,n):if nums[j]>nums[dp[i][j-1]]:dp…
题目:
A robot is located at the top-left corner of a m x n grid (marked Start in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked Fi…
题目:
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[[2],[3,4],[6,5,7],[4,1,8,3]
]
The minimum path sum from top to bott…
梅丽渡题目信息输入输出注测试样例解答题目信息
众所周知,strawberry的妹子很多而且总数甚至是不可数的,妹子集合和阿列夫零等势。 今天strawberry把他的 n 个妹子带来,排成一排。strawberry的妹子很多,但是质量不容乐观。每个妹…
方向标题目信息输入输出注测试样例解答题目信息
A carpenter has received an order for a wooden directional sign. Each board must be aligned vertically with the previous one, either to the basis of the previous arrowhead or to the opposite side, being fixed t…
LeetCode链接
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的…
347 前 K 个高频元素题目给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。思路具体代码实现(C)模型(知识点)题目
给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频…
//Archimedes
#include<iostream>
#include<cmath>
using namespace std;int main()
{const double y 62.4;const double pi 3.1415926;double weigth,radius,volume,fb;cout<<"输入球的重量和半径:\n";cin>>weigth>>rad…
Conversion of feet/inches to meters-英尺、英里装换为米,允许重复计算://Conversion of feet/inches to meters-英尺、英里装换为米,允许重复计算
#include<iostream>
#include<cmath>using namespace std;void get_input(doub…
https://acs.jxnu.edu.cn/problem/NOIOPJENGLISH15
Sum is K 1000ms 65536K
描述:
Given a sequence of N numbers. Find different numbers A and B in the sequence so that the sum of A and B equals to K.
(给定一行N个数字。找到在这行数字里…
代码随想录刷题60Day 目录
前言
不同路径
不同路径(2) 前言
今天的动态规划题与昨天的题很类似,只不过今天的题是在二维上讨论,难度上略有提升。 不同路径 int uniquePaths(int m, int n) {vector<int> dp(n 1, 1);for (int i 1; i < m; …
题目链接: https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 …
裁玻璃
#include<bits/stdc.h>
#define intn long long
using namespace std;
int dp[1100][1100],a[1100],s[1100];
int getsum(int s)
{int res0;while(s){if(s&1)res;s>>1;}return res;
}
int judge1(int s1,int sd)
{if((s1&sd)||(s1<<1)&s…
贪心策略_区间选点问题
基本做法
Description
You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn. Write a program that: reads the number of intervals, their end points and integers c1, …, cn from the standard input, computes the …
小蒜想知道把 MM 个同样的苹果放在 NN 个同样的盘子里,允许有的盘子空着不放,共有多少种不同的分法?(用 KK 表示)55,11,11 和 11,55,11 是同一种分法。
输入格式 第一行…
目录
欧几里得算法
质数筛
欧拉函数 矩阵乘法的实现 欧几里得算法
欧几里得算法又称辗转相除法。该算法用来快速计算2个整数的最大公约数 公式:gcd(a,b)gcd(b,a mod b)
int gcd(int a, int b) {if (b 0)return a;return gcd(b, a % b);
} 计算最小公倍数也通…
A. tokitsukaze and Connection 题目链接 题意:给你一个全由小写字母构成的字符串,判断这个字符串中的同种字母是不是全部连在一起; 思路:直接暴力for一遍,从第二个字母开始,判断当前字母有没有出现过&…
题目输入凸 n 边形 p 1 ,p 2 , ,p n , 其中顶点按凸多边形边界的逆时针序给出,多边形中不相邻顶点间的连线称
为弦。试设计一个动态规划算法,用若干条弦将凸边形 p 1 ,p 2 , ,p n 剖分成一些无公共区域的三角形,使
得所有三角形的周长之和最小…
problem cf 1800 由于每一位的和和顺序无关,所以枚举即可, 时间复杂度O(nlogn)O(nlogn)O(nlogn)
// Decline is inevitable,
// Romance will last forever.
#include <bits/stdc.h>
using namespace std;
//#define mp make_pair
#define pii pa…
1. 最长递增子序列 LIS (中等)
地址: https://leetcode-cn.com/problems/longest-increasing-subsequence/ 2021/12/26 做题反思:
class Solution {public int lengthOfLIS(int[] nums) {int n nums.length;int[] dp new int[n];Arrays.f…
javascript递归This blog will give an intro explanation of recursion in javascript.该博客将介绍javascript中的递归解释。 Recursion is the act of calling a function on itself. This allows you to recurse, or iterate over the parameter passed in while holding …
没看答案
class Solution {
public:int findLength(vector<int>& A, vector<int>& B) {int m A.size();int n B.size();vector<vector<int>> dp(m, vector<int>(n));int res 0;for(int i 0; i < m; i){if(B[0] A[i]){dp[i][0] …

/*VF 时间限制:1000 ms | 内存限制:65535 KB 难度:2 描述 Vasya is the beginning mathematician. He decided to make an important contribution to the science and to become famous all over the world. Bu…
01背包问题 有 NN 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 ii 件物品的体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 #include <bits/stdc.h>us…
题目
Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1: Input: “bbbab” Output: 4 One possible longest palindromic subsequence is “bbbb”.Example 2: Input: “…
Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子,每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ,其中 stones[i] 是第 i 个石子的价值。
Alice 和 Bob 轮流进行自己的回合,Alice 先手。每一回合ÿ…
题目地址:https://leetcode.com/problems/flood-fill/description/解题思路:深度优先搜索code(java):public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {int oldColor image[sr][sc];if (oldC…
https://codeforces.com/contest/4/problem/D 题目大意
给定 n n n 个信封的长和宽,以及一张卡片的长和宽,要求选出最多的信封,并且这些信封的长和宽都比前面的信封要大,并且最小的信封能够装下这张卡片。输出这些信封的数量和…
目录1.题目2.思路3.代码实现(Java)1.题目
在 x 轴上有一个一维的花园。花园长度为 n,从点 0 开始,到点 n 结束。
花园里总共有 n 1 个水龙头,分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n 1 的整数数…
完全平方数https://leetcode-cn.com/problems/perfect-squares/ 题目描述: 思路分析:四平方和定理 class Solution {
public:// 判断是否为完全平方数bool isPerfectSquare(int x) {int y sqrt(x);return y * y x;}// 判断是否能表示为 4^k*(8m7)bool…
有一棵 n n n 个节点的以 1 1 1 号点为根的有根树。现在可以对这棵树进行若干次操作,每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。
现在我们想知道对于每一个 k k k ( 1 ≤ k ≤ n 1≤k≤n 1≤k≤n),最少需要多少次操作能…
不同的二叉搜索数https://leetcode-cn.com/problems/unique-binary-search-trees/ 题目描述:
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
思路:…
91. 解码方法(中等) 思路 这其实是一道字符串类的动态规划题,不难发现对于字符串s的某个位置i而言,我们只关心「位置 i 自己能否形成独立 item」和「位置 i 能够与上一位置(i-1)能否形成item 」,…
这次考的是 A t C o d e r AtCoder AtCoder的题 发挥不是很好 用洛谷当题面了 还能方便点
A
直接七天一求和就行
#include<bits/stdc.h>
#define reg register
using namespace std;
inline void read(int &x){int s0,w1;char chgetchar();while(ch<0||ch>9…
给你一个整数 n ,对于 0 < i < n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n 1 的数组ans 作为答案。 class Solution {
public:vector<int> countBits(int n) {//题目要求长度为 n 1 的数组 ansvector<in…
背包九讲 0-1 knapsack problem
01背包-牛客网
已知一个背包最多能容纳体积之和为V的物品,现有 n 个物品,第 i 个物品的体积为 vi , 重量为 wi,求当前背包最多能装多大重量的物品?
使用动态规划来解决01背包问题:
…
Day12
自增自减运算符
int b a; //先给b赋值,再自增 int c a; //先自增,再给b赋值 package operater;public class Demo04 {public static void main(String[] args) {// -- 自增,自减 一元运算符 只有一个未知数int a 3;int b a…
最长上升子序列模型
题目描述 给定一个长度为 NN 的数列,求数值严格单调递增的子序列的长度最长是多少。 思路分析
分析:最长上升子序列模型经典问题,经典解法。 C实现
#include <bits/stdc.h>using namespace std;const int N 101…
模板题目
#include <bits/stdc.h>
#define ll long long
#define pr pair<int int>using namespace std;const int maxn1e310;
int n,m,ans,ecnt;int f[maxn][maxn]; int w[maxn],v[maxn];
int b[maxn];
int s[maxn][maxn]; int main()
{cin>>m>>n;in…
LeetCode740. 删除并获得点数
2021.5.5每日一题,动态规划,我的思路如下
class Solution {public int deleteAndEarn(int[] nums) {//看到题想到了动态规划,但是怎么规又是个问题,先排序应该没问题//dp[i]定义为到当前为止&#…
A - Vacations
对不起,这题我写过hh,ctrlc完事。DP一下就行了。
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[105][3]{0};
int main(){int n,toda;scanf("%d",&n);for(int i1;i<n;i){scanf(&qu…
赛时没发挥好6题金尾(rank38),剩下很多能写的题,其中四个dp,傻眼ing
A Girls Band Party(背包)
有点迷惑的题,当时看只要 5 5 5 张牌一下子想到暴力枚举,结果发现是不…
动态规划算法
代码
import java.util.Scanner;public class DP {public static int matrixChaain(int []p, int [][]m, int [][]s){// m[i][j]代表从第i到j之间的矩阵的最小连乘数int n p.length-1; // 当前矩阵的个数for(int i1;i<n;i) m[i][i]0; //对角线的值初始化为…
583. 两个字符串的删除操作
题目描述
给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个字符。 示例1: 输入: w o r d 1 " s e a " , w o r d 2 " e a t …
0,1背包
#include<bits/stdc++.h>
using namespace std;
struct BONE{int val;//物体价值 int vol;//物体重量
}bone[1011];int T,N,V;
int dp[1011][1011];
int ans(){memset(dp,0,sizeof(dp));for(int i=1;i<=N;i++)for(int j=0;j<=V;j++){if(bone[i].vol>…
分组背包(模板题) 有 N 组物品和一个容量是 V 的背包。 每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。 求解将哪些物品装入背包&#x…
Count the string HDU - 3336 It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example: s: “abab” The prefixes are: “a”…
设计算法,递归的计算二叉树的高度
1)算法思想
2)伪代码
int TreeDepth(TreeNode root) { if(rootnull) return 0; int left TreeDepth(root.left); int right TreeDepth(root.right); return Math.max(…
动态规划part051049. 最后一块石头的重量 II题目描述思路总结494. 目标和题目描述思路回溯算法动态规划总结474.一和零题目描述思路总结1049. 最后一块石头的重量 II
题目链接:1049. 最后一块石头的重量 II 参考:https://programmercarl.com/1049.%E6%9…
1、Z 字形变换(字符串)
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
P A H N
A P L S I I G …
分隔数组以得到最大和 d p [ i ] dp[i] dp[i]表示前i个数字的最大和,k种转移。 d p [ i ] m a x { d p [ i − 1 ] 1 ∗ m a x { a r r [ i ] } d p [ i − 2 ] 2 ∗ m a x { a r r [ i ] , a r r [ i − 1 ] } . . . k ∗ d p [ i − k ] m a x { a r r [ i ] …
2022.2.10 练习 PAT 甲 1068 Find More Coins (原题链接)
背包问题
#include <bits/stdc.h>
using namespace std;
int c[10010];
int dp[10010]{0};
int choice[10010][110];
int flag[10010];bool cmp(int a,int b)
{return a>b;
}int main…
2022.2.10 练习 PAT 甲 1007 Maximum Subsequence Sum (原题链接)
#include <bits/stdc.h>
using namespace std;
int a[10010];
int dp[10010];int main()
{std::ios::sync_with_stdio(false);int n;cin>>n;int num0;for(int i0;i<n;i)…
状态压缩dp 如果本来就在关系网之内,最小步是0,上一个状态是-1(不存在) 如果通过新的关系到达的步骤小于之前的步骤,就更新。
#include <iostream>
#include <cstring>
using namespace std;
const int init-1;
int minstep[1…
大盗阿福
题目
链接:https://www.acwing.com/problem/content/1051/
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N N N 家店铺,每家店中都有一些现金。
阿福事先调查得知,只…
这个题是《计算之魂》里边的一个问答题,完全不会呀,问一下AI怎么解决:
有几种方法可以加到9的问题可以使用递归或动态规划来解决。以下是一种使用动态规划的方法:
我们定义一个数组 d p [ i ] dp[i] dp[i],其中 d …
题目
POJ2955.Brackets We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence, if sss is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and if aaa and…
文章目录 Greatest Sum Divisible by Three 可被三整除的最大和-动态规划问题描述:分析代码 Tag Greatest Sum Divisible by Three 可被三整除的最大和-动态规划
问题描述:
给你一个整数数组 nums,请你找出并返回能被三整除的元素最大和。 …
【Q108】(md) 有序矩阵中第k小的元素 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是排序后的第 k 小元素,而不是第 k 个不同的元素。 示例: matrix [ [ 1, 5, 9 …
常用算法的计算复杂度穷举法 (Method of Exhaustion)二分法 (Bisection)线性规划(LP)半定规划(SDP)逐次凸逼近(SCA)块坐标下降(BCD)内…
多重背包问题(二进制优化) 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 输出最大价…
不同路径https://leetcode-cn.com/problems/unique-paths/ 题目描述:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中…
分析
先不考虑瞬移功能,设fif_ifi表示i位置上的最多的飞行次数,那么我们可以线通过单调栈预处理出来每个位置 i ,左侧和右侧第一个比它高的位置,分别记为lp[i]和rp[i],那么转移方程为fimax{fj1∣lp[i]≤j≤rp[i]}f_…
本题要求对两个整数a和b,输出其中较大的数。
函数接口定义: int max( int a, int b ); 其中a和b是用户传入的参数,函数返回的是两者中较大的数。
裁判测试程序样例:
#include <stdio.h>int max( int a, int b );int main…
n中p的倍数元素的个数 n/p下取整
如果是2 和 3 的倍数 就是6的倍数 n/6下取整 #include<iostream>
using namespace std;typedef long long LL;
const int N20;
int p[N],n,m;int main()
{cin>>n>>m;for(int i0;i<m;i) cin>>p[i];int res0;for(int…
Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.
The game can be played by two or more than two players. It consist…
题目链接点击打开链接Apple CatchingTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 12916 Accepted: 6274 Description It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his f…
题目:310:Is It A Tree?(OpenJudge - 310:Is It A Tree?)
翻译:
树是一种众所周知的数据结构,它要么是空的(null, void, nothing),要么是由满足以下属性的节点之间的有向边连接的一个或多个节点的集合。…
题目
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
示例 1:
输入:s “rabbbit”, t “rabbit” 输出:3 解释: 如下所示, 有 3 种可以从 s 中…
首先附上模板:
#include<bits/stdc.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl \nusing namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N 100010;int n;
int a[N], q[N];int main()…
分割回文串 II
力扣链接:132. 分割回文串 II
题目描述
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 Java代码
class Solution {public int minCut(String s) {int n s.leng…
1.排序算法分类 **比较类算法排序:**通过比较来决定元素的时间复杂度的相对次序,由于其时间复杂度不能突破 O ( n l o g n ) O(nlogn) O(nlogn),因此也称为非线性时间比较类算法 **非比较类算法排序:**不通过比较来决定元素间的…
题目链接:石子合并 #include <iostream>
#include <algorithm>using namespace std;const int N 310, INF 1e9;int n;
// 前缀和
int s[N];
int f[N][N];int main()
{cin >> n;for(int i 1; i < n; i ) cin >> s[i];for(int i 1; i …
题目描述: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。那…
0x55 环形与后效性处理
休息时间
题意:
一天有 n n n 个小时,在第 i i i 个小时睡觉恢复体力 u i u_i ui。一头牛一天要休息 b b b 个小时,可以分成多段。每一段需要花费一个小时才能睡着,这一个小时不恢复体力。询问恢复…
A - 数塔
给你一个数字金字塔,每个节点有值a,求根节点到叶节点的值的最大和
以矩阵的方式存储,有:
dp[i][j]=a[i][j]+max(dp[i−1][j],dp[i−1][j−1])
#include <cstdio>
#include <cstring>
int a[105][105],dp[105][105];
int main(){int t,n…
貌似是我做的第一道dp题,hh岁月如水,很简单就不说啥了
#include <cstdio>
long long step[25][25];
bool map[25][25];
int main(){int b1,b2,m1,m2;scanf("%d%d%d%d",&b1,&b2,&m1,&m2);map[m1][m2]map[m1-1][m22]map[…
要么第一间房子被抢最后一间不抢;要么最后一间房子被抢第一间不抢。所以构造两个dp数组,dp_first忽视最后一间房子,dp_last忽视第一件房子。
python
class Solution:def rob(self, nums: List[int]):n len(nums)if n 0:return 0if n in […
文章目录已整理未整理P2602 数字计数 数位DPPOJ 2282 The Counting Problem 数位DPHDU3555 Bomb 数位DPPOJ3252 Round Numbers 数位DPPOJ 3311 Hie with the Pie 状态压缩DP已整理
【题目记录】——第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛&…
(2) 114. 不同的路径 public class Solution {/*** param m: positive integer (1 < m < 100)* param n: positive integer (1 < n < 100)* return: An integer*/public int uniquePaths(int m, int n) {// write your code hereint[][] res new int[m][n];for(…
题目链接:https://ac.nowcoder.com/acm/contest/329/G
题目大意:输入两个数l,r,求l到r之前所有不含6的数有几个。
代码:
#include <bits/stdc.h>
using namespace std;
typedef long long ll;int a[20];
ll d…
⭐欢迎来到剑指offer好题精选专栏,一起学习,一起进步⭐ 题目信息: 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下ÿ…
斐波那契数列模型以及多状态 动态规划简述斐波那契数列模型1.第 N 个泰波那契数(简单)2.三步问题(简单)3.使⽤最⼩花费爬楼梯(简单)4.解码方法(中等) 简单多状态1.打家劫舍ÿ…
Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni1, …, Nj } where 1 < i < j < K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, giv…
Prufer序列
起源于对 C a y l e y Cayley Cayley定理的证明,但是其功能远不止于此 现在考虑将一棵n个节点的树与一个长度为n-2的prufer序列构造对应关系 T r e e − > P r u f e r : Tree->Prufer: Tree−>Prufer: ①从树上选择编号最小的叶子节点&#x…
最后一块石头的重量 II 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果如下&am…
矩阵连乘
题目描述 解题代码
void printOptimalParens(vector<vector<int>>& partition, int i, int j) {if (i j) cout << "A" << i; // 单个矩阵,无需划分else {cout << "(";printOptimalParens(partit…
1444. 切披萨的方案数
困难118
给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: A (表示苹果)和 . (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。
切…
A 统计和小于目标的下标对数目 数据量小,直接枚举数对 class Solution {
public:int countPairs(vector<int> &nums, int target) {int n nums.size();int res 0;for (int i 0; i < n; i)for (int j 0; j < i; j)if (nums[i] nums[j] < tar…
解题步骤: 参考代码:
未优化代码:
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {//开一个三维的dp表vector<vector<vector<int>>> dp(strs.size()1,vector<vector<in…
题目链接 Leetcode.740 删除并获得点数 mid 题目描述
给你一个整数数组 n u m s nums nums ,你可以对它进行一些操作。
每次操作中,选择任意一个 n u m s [ i ] nums[i] nums[i] ,删除它并获得 n u m s [ i ] nums[i] nums[i] 的点数。之…
代码:
class Solution {public int minFallingPathSum(int[][] matrix) {int n matrix.length;if(n1){return matrix[0][0];}int[][] sum new int[n][n];for(int i0;i<n;i){sum[0][i] matrix[0][i];}for(int i1;i<n;i){for(int j1;j<n-1;j){sum[i][j] …
引
好歹第一次正经学状压,好好总结一下
T1 [CQOI2018] 解锁屏幕
题目传送门
解法
状态设计: f S , i : 连上了 S 中的所有的点并且当前处于 i 点的方案数 f_{S,i} : 连上了S中的所有的点并且当前处于i点的方案数 fS,i:连上了S中的所有的点并且当…
LCR 089.打家劫舍
Python:
class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""n=len(nums)if nums ==0 or n==0:return 0dp=[[0 for _ in range (2)] for _ in range(n)]dp[0][0]=0dp[0][1]=nums[0]for i in…
「KDOI-06-S」树上异或
题目描述
给定一棵包含 n n n 个节点的树,第 i i i 个点有一个点权 x i x_i xi。
对于树上的 n − 1 n-1 n−1 条边,每条边选择删除或不删除,有 2 n − 1 2^{n-1} 2n−1 种选择是否删除每条边的方案。
对于…
传送门:AtCoder Regular Contest 163 - AtCoder 第一题我们只需要将字符串分成两段,如果存在前面一段比后面一段大就成立。
#include<bits/stdc.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int&g…
01背包总结 背包可以不装满
题干:
Weight[N] , Value[N], backSize
解释:
有N件物品,重量存放在Weight[]数组中,价值存放在Value[]数组中。即第 i i i件物品对应的重量为 W e i g h t [ i ] Weight[i] Weight[i] ,价值为 V …
一、LeetCoed62. 不同路径
题目链接:62. 不同路径
题目描述:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下…
题目:
2304. 网格中的最小路径代价
给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中,从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) …
一、LeetCode1049. 最后一块石头的重量 II
题目链接:1049. 最后一块石头的重量 II
题目描述:
有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将…
论文作者:Robert G. Haight, Charles S. Revelle, Stephanie A. Snyder 论文原文:Robert G. Haight, Charles S. Revelle, Stephanie A. Snyder, (2000) An Integer Optimization Approach to a Probabilistic Reserve Site Selection Problem. Operat…
2023年12月-2024年2月召开会议汇总: The 16th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2023)
Location: Virtual
Important dates:
Conference: December 11, 2023 (Start) - December 13, 2023 (End)
Details…
原文信息:MindOpt Tuner: Boost the Performance of Numerical Software by Automatic Parameter Tuning 作者:王孟昌 (达摩院决策智能实验室MindOpt团队成员) 一个算法开发者,可能会幻想进入这样的境界:算…
题目
描述
We consider a string to be a good string if and only if the string contains no palindromic substrings of length greater than 2 Now we want to know how many different good strings are there for all strings of exactly n length and character set s…
一和零 中等 817 相关企业 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1:
输入…
https://leetcode.cn/problems/ones-and-zeroes/description/
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的…
World Final? World Cup! (I)后面不用踢当且仅当即便后面全进,也赶不上另一方,注意还能踢几次球的计算AC代码:#include <bits/stdc.h>
using namespace std;
using LL long long;
int main() {ios::sync_with_stdio(false);cin.tie(n…
343 整数拆分 medium 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k > 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 这道题乍一看没有点儿动态规划的影子,反而感觉用数学法可以求解。
但是…
leetcode 139.单词拆分leetcode 139.单词拆分给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明:拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1&…
647. 回文子串方法:双指针回文子串有长度为奇数和偶数两种,extend(s, i, i, n); extend(s, i, i 1, n);就分别对应长度为奇数和偶数的情况class Solution {
private:int extend(const string& s, int i, int j, int n) {int res 0;while (i > 0…
一. 原题呈现及解读
原题目:leetcode 1641. 统计字典序元音字符串的数目
给你一个整数 n,请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足:对于所有有效的 i,…
题目:
给你整数 zero ,one ,low 和 high ,我们从空字符串开始构造一个字符串,每一步执行下面操作中的一种:
将 ‘0’ 在字符串末尾添加 zero 次。 将 ‘1’ 在字符串末尾添加 one 次。 以上操作可以执行任…
适用场景
题目链接:数字三角形
/*正推DP,可能数据比较小,这个正推不太麻烦可以AC*/
#include<bits/stdc.h>
using namespace std;
int r;
int a[1005][1005],f[1005][1005];int main(){cin>>r;for(int i1;i<r;i){for(int j1…
题目: 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1: 输入:…
题目
转换问题:所有人把钱放在桌上,每个人拿走自己所需的钱。 每个人并不需要重复的把相同钞票放在桌子上再拿回来,因此对于第 i i i 种钞票,假设 A A A 初始有 x x x 张,结束有 x ′ x x′ 张, A A A…
LINK
不得不说 双指针用法nb
题目 输入输出样例
输入 6 3 1 5 2 1 7 3 1 3 8 输出 3
思路:
建议看尺取法
代码:
#include<bits/stdc.h>
using namespace std;
typedef long long ll;
//#define int long long
const int mod1e97;
const int…
Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined to be { Ni, Ni1, ..., Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequenc…
题意描述:
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没…
目录
138. 复制带随机指针的链表 Copy List with Random-pointer 🌟🌟
139. 单词拆分 Word Break 🌟🌟
140. 单词拆分 II Word Break II 🌟🌟🌟
🌟 每日一练刷题专栏 &…
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 思路:动态规划 F(i,n)表示以i为根节点,n为长度的构成的总数。 G(n)表示长度为n构成的总数。 G(n)F(i,n…
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# dp[i][j]表示text1[:i1]与text2[:j1]的最长公共子序列dp [[0]*(len(text2)1) for _ in range(len(text1)1)]for i in range(1,len(text1)1):for j in range(1,len(text2)1):if text1[…
LINK
题目 思路: 先将每个人拥有的桃子数量减1,再将其求出前缀和(求的同时直接modk)先将每个人拥有的桃子数量减1,再将其求出前缀和(求的同时直接mod k)先将每个人拥有的桃子数量减1,再将其求出前缀和&…
70,爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 简单题:设第n阶的方法为 f ( x ) f(x) f(x),则有 f ( x ) f ( x − 1 ) f ( x 2 ) f(x)f(x-1)f(x2) f(x)f(x−1)f(x2) 代…
8.树形DP
没有上司的舞会
树上最大独立集问题
Ural 大学有 N N N 名职员,编号为 1 ∼ N 1 \sim N 1∼N。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数 H i H_i Hi 给出,…
第十五周作业 目录 MT2147 纸带MT2148 围栏木桩MT2152 抽奖MT2153 异或和MT2154 海龟 MT2147 纸带 难度:钻石 时间限制:2秒 占用内存:128M 题目描述 小码哥有一张 1 n 1\times n 1n 的纸带,由 n n n 个格子组成。初始…
最长公共子序列
代码(附分析过程)
import java.util.Scanner;public class one {// DP求解最长公共子序列public static int LcsLength(char[] x, char[] y, int[][] vis) {int m x.length - 1;int n y.length - 1;int[][] c new int[m 1][n 1]; …
求ab mod n
因为a mod n b mod n可能超过int 所以用long long 保存中间值
// ab mod n
int mul_mod(int a, int b, int n) {a % n, b % n;return (int)((long long)a * b % n);
}
大整数取模
输入正整数 n 和 m ,输出 n mod m 的值
// n mod m
scanf("%s…
不同路径二https://leetcode-cn.com/problems/unique-paths-ii/ 题目描述:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下…
Introduction
单应矩阵估计方法(传统deep learning) 本文的工作 auxiliary loss function: compares the dynamic mask from the ground-truth dynamics map that is estimated from the training data.
Related Work
1.Pixel-based approaches
直接…
给定两个字符串s_1s_2...s_ns1s2...sn和t_1t_2...t_nt1t2...tn.求出这两个字符串的最长公共子序列的长度。
输入
输入第一行有两个整数mm和nn,分别表示字符串ss和tt的长度,输入第二行和第三行分别表示字符串s和t.1 \leq n, m \leq 10001≤n,m≤1000.
输出
对于每…
题目:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:
[[…
题:最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。示例:
输入:
[[1,3,1],[1,5,1],[4,2,1]
]
输出: 7
解释: 因为路径 1→3→…
给定两个字符串 A 和 B,现在要将 A 经过若干操作变为 B,可进行的操作有: 1.删除–将字符串 A 中的某个字符删除。 2.插入–在字符串 A 的某个位置插入某个字符。 3.替换–将字符串 A 中的某个字符替换为另一个字符。 现在请你求出,…
Problem - C - Codeforces
题目意思 你有2台电视,问你能不能看完视频
解题思路
可以定义两个变量 如果俩个变量在看电视但是下一个节目开始了,那就说明看不完全部节目
#include"bits/stdc.h"
#define ll long long
#define pi pair<int…
【解题思路】 dp[i1] max{dp[i] nums[i],nums[i]};最大是子数组和是前一个最大子数组和与当前数字中较大的值。
class Solution {public int maxSubArray(int[] nums) {int len nums.length;int[] dp new int[len1];int max -99999;for(int i 0; …
文章目录 前期知识516. 最长回文子序列思路1——转换问题:求 s 和反转后 s 的 LCS(最长公共子序列)思路2——区间DP:从两侧向内缩小问题规模补充:记忆化搜索代码 1039. 多边形三角剖分的最低得分从记忆化搜索开始翻译成…
题目
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: f…
1、n个数的全排列问题。
代码 public class one {// 交换函数public static void swap(char[] array, int i, int j) {char temp array[i];array[i] array[j];array[j] temp;}// 全排列函数public static void fun(char[] array, int p) {if (p array.length) { //当前为最…
面试题58:反转字符串
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. “,则输出"student. a am I”。
calss S…
给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多…
KMP算法主要是用来求解子串在主串中第一次出现的位置,并返回这个子串的位置的一种提高效率的方法。在讲解KMP算法之前,我们先来看看求子串在主串中位置的一般解法,即暴力解法。 1.暴力解法 public static int BF(String str,String sub){if(s…
2021/12/11
剑指 Offer II 099
最小路径之和 传送门:II 099
给定一个包含非负整数的 m x n 网格 grid , 请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小
示例 1:输入:grid [[1,3,1],[1,5,1],[4,2…
LCS模板
#include <bits/stdc.h>
using namespace std;
const int N 1000;
int dp[N][N];
char A[N], B[N];
int main()
{fgets(A 1, N, stdin);fgets(B 1, N, stdin);int lenA strlen(A1);int lenB strlen(B1);for(int i 0; i < lenA; i){dp[i][0] 0;}for(in…
固定模板
不记录路径
#include <bits/stdc.h>
using namespace std;
const int N 100;
int A[N], dp[N];//以A[i]为结尾的最长不下降子序列
int main()
{int n;cin >> n;for(int i 1; i < n; i){cin >> A[i];}int ans -1;for(int i 1; i < n; i)…
题目链接点击打开链接Cow BowlingTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 19704 Accepted: 13056 Description The cows dont use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a s…
传送门:HDU 3591 题目大意:小倩去买一件价值为 t 东西,她有 n 种钱币,第i种价值为 Vi,数量为 Ci。售货员那也有这 n 种货币,但是数量无限。如果小倩付款给的价值大于 t,售货员就要找零。问小倩…
给你一串一维数组 假如取a1 就不能取 a2 , 如果取a2 , 就不能取a1, a3 ,不能取相邻的数字
#include "bits/stdc.h"
#define ll long long
using namespace std;
int s[100005];
int dp[100005];
int n;
int main()
{while (cin >> n){memset(s,0,sizeof s);…
541 反转字符串 II题目给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个,则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个,…
滑动窗口
还可以
# 单调减-找最大值
n,k map(int,input().split())
nums list(map(int,input().split()))
N 1000010
q [0]*Nhh,tt 0,-1
q[0]*N
for i in range(n):if tt>hh and i-q[hh]1>k:hh 1while tt>hh and nums[i]<nums[q[tt]]:tt - 1tt 1q[tt] ii…
一、题目
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。 二、思路 三、实现
/*** param {number[][]} grid* return {number}*/
var min…
一、题目1:对角线遍历I
(1)题目
给你一个大小为 m x n 的矩阵 mat ,请以对角线遍历的顺序,用一个数组返回这个矩阵中的所有元素。 (2)思路
根据题目描述,首先仔细找一下这道题中一…
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid1087 Super Jumping! Jumping! Jumping! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 47055 Accepted Submission(s): 21755 Problem Desc…
题目
You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols and -. For each integer, you should choose one from and - as its new symbol. Find out how many ways to assign symbols to make sum of integers eq…
kotlin 尾递归阶乘Given a number, we have to find its factorial using recursion. 给定一个数字,我们必须使用递归来找到它的阶乘。 Example: 例: Input:5Output:120在Kotlin中使用递归程序查找给定数字的阶乘 (Program to find factorial of a giv…
文章目录A - Wrestling Match 并查集C - Game of Taking Stones 威佐夫博弈 高精度D - A Simple Math Problem 数学F- Detachment 数学 前缀和 前缀积H - To begin or not to begin 数学概率J - Find Small A 进制转换K - Guess the number题目集地址
ICPC大连2016A - Wrestlin…
文章目录A Girls Band Party 分组背包B So Easy 思维DEG Pot!! 线段树I Base62 进制转换 数学 大数KN Fibonacci Sequence 简单题题目集地址
2019ICCPC银川参考题解
2019 ICPC亚洲区域赛银川赛区题解A Girls Band Party 分组背包
题目地址A Girls Band Party 参考文章Girls Ba…
文章目录A A Hard ProblemC Digital Path 记忆化搜索H Prince and PrincessK Triangle题目集地址
南京2019区域赛A A Hard Problem
题目地址 A A Hard Problem 题目大意:给出一个正整数n,找到一个最小的整数k使得集合1,2,…n{1,2,\dots n}1,2,…n的任意…
范文:
亮点: has been acknowledged 被认为 From my perspective 在我看来 modern parents are more related to 更加被加入 emphasis z重视 to some extent 可以代替somehow That could suggest 可以和imply互相代替着用 arrangements/apportionment分配、规划 pe…
Problem Description穿过幽谷意味着离大魔王lemon已经无限接近了!可谁能想到,yifenfei在斩杀了一些虾兵蟹将后,却再次面临命运大迷宫的考验,这是魔王lemon设下的又一个机关。要知道,不论何人,若在迷宫中被困…
菜鸡记录站A、Welcome代码B、第K大元素代码C、整数划分问题之备忘录法代码D、数字三角形之备忘录法代码E、数字三角形之动态规划法代码F、滚球游戏代码A、Welcome
题目描述
”How happy we are, To meet friends from afar!” Welcome to Hunan University of Chinese Medici…
没看答案,可以交易最多两次。
labuladong版
import sysclass Solution:def maxProfit(self, prices: List[int]) -> int:n len(prices)k 2dp [[[0] * 2 for _ in range(k1)] for _ in range(n)]for i in range(n):dp[i][0][0] 0dp[i][0][1] -sys.maxsizef…
python 构件二维数组Arrays in JavaScript are something special, as they leverage the prototype feature of JS and provide a handy way to run functions directly from a reference to an array instance.JavaScript中的数组很特别,因为它们利用了JS的原型功…
题目 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols and-. For each integer, you should choose one from and- as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal …
原网址:https://acs.jxnu.edu.cn/problem/NOIOPJCH02077215
描述:
Huanhuan challenges you to a simple math problem.
Define F(x)F(x) as the sum of the decimal digits of xx.
//嬛嬛给你一个简单的数学问题。
定义F(x)F(x)是十进制…
没看答案,允许交易k次。
labuladong版
import sysclass Solution:def maxProfit(self, k: int, prices: List[int]) -> int:n len(prices)if n < k or k 0:return 0dp [[[0] * 2 for _ in range(k1)] for _ in range(n)]for i in range(n):dp[i][0][0] …
LeetCode 062、不同路径
题目 题解
按照动态规划五部曲来分析。 class Solution {
public:int uniquePaths(int m, int n) {if (m < 0 || n < 0) return 0;vector<vector<int>> dp(m, vector<int>(n));for (int i 0; i < m; i) dp[i][0] 1; //…
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1&a…
没看答案,可以交易无数次,但是卖出后的第二天不可以买入。
labuladong版(超时)
import sysclass Solution:def maxProfit(self, prices: List[int]) -> int:n k len(prices)dp [[[0] * 2 for _ in range(k1)] for _ in ra…
01背包
int dp[10000];
int v[100];
int p[100];
int main()
{ int n,w;cin>>n>>w;for(int i1;i<n;i){cin>>v[i]>>p[i];}for(int i1;i<n;i){for(int jw;j>0;j--){if(j>v[i])dp[j]max(dp[j],dp[j-v[i]]p[i]);}}cout<<dp[w];
} …
LeetCode-62. 不同路径
难度:中等
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。…
动态规划题集2
1. 互不侵犯King
题目:在 N N NN NN 的棋盘里面放 K K K 个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共 8 8 8 个格子。…
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a b c 0 并找出所有满足条件且不重复的三元组。
题目使用双指针法进行求解,求解思路如下:
1.将数组进行排序
2.i从下表…
可转化为01背包问题,sum为N,neg为dp[-1][-1]。 class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:N, n sum(stones), len(stones)target N // 2dp [[0] * (target1) for _ in range(n)]for j in range(target1):if j > s…
最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。
public class A {private static int getCommonStrLength(String str1, String str2) {//创建一个二维数组大小,行列…
Link
思路
首先把所有工匠按 SiS_iSi 从小到大排序,保证能按顺序进行线性dp 设 f[i][j] 表示安排前 iii 个人粉刷前 jjj 块木板(可以有空着不刷的木板),工匠们能获得的最多报酬。
第 i 个工匠什么也不刷,f[i][j]…
没看答案,可以交易无数次。
labuladong版(超时)
import sysclass Solution:def maxProfit(self, prices: List[int]) -> int:n k len(prices)dp [[[0] * 2 for _ in range(k1)] for _ in range(n)]for i in range(k1):dp[-1][i][0] …
class Solution:def uniquePaths(self, m: int, n: int) -> int:dp [[0] * n for i in range(m)]for i in range(m):dp[i][0] 1for j in range(n):dp[0][j] 1for i in range(1, m):for j in range(1, n):dp[i][j] dp[i-1][j] dp[i][j-1]return dp[-1][-1]
POJ - 3254 Corn Fields
题目链接
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the square…
1.The Biggest Water Problem 思路:直接暴力,但是后来发现标签是递归; 暴力代码
#include <bits/stdc.h>
using namespace std;
const int N1e6;
int n,m;
void solve()
{cin>>n;while(n>9){int ans0;while(n>0){ansn%10;…
1592E2
// Decline is inevitable,
// Romance will last forever.
#include <bits/stdc.h>
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define ll long lo…
题面 题解 代码
#include<bits/stdc.h>using namespace std;
const int N 1e3 10;int n;
int a[N];
int f[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);cin >> n;for (int i 1; i < n; i) cin >> a[i];for (int i 1; i …
Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information
Year: 1981 Authors: Michael Zuker and Patrick Stiegler Journal Name: Nucleic Acids Research
Motivation
将动态规划算法与热动力学数据结合。
Research Objective …
LeetCode 64.最短路径和 给定一个包含非负整数的 m x n 矩阵 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 类似题 剑指offerII 47.礼物的最大价值 LeetCode 120.三角形最小路…
LeetCode每日一题(2021-3-7 & 3-8 分割回文串 I & II)
题目 I 描述 这两道题是一个系列(还有III和IV,暂时先不管),两道题的区别在于,I是返回 s 所有可能的分割方案(输入输出…
A. Book
题意:
给出n本书,对于每本书给出ki个数,你能理解第i本书当且仅当你全部读过这ki本书,问读多少轮可以理解全部的书,1轮指1-n都读一遍。若无法理解 则输出-1。
思路:
不难想到拓扑排序࿰…
Link 实数下线性基
#define double long double
double a[N][N];
struct node {double a[550];int w;bool operator < (const node &x) const {return w < x.w;}
}p[550];
int n, m;
double b[N][N];
bool insert(int m, double c[]) {for(int i m-1; i > 0; i-…
547. 朋友圈
经过路径压缩的并查集,时间复杂度近似看成O(1)
时间复杂度:O(n2)
空间复杂度:O(n)
class Solution {public int findCircleNum(int[][] M) {Disjoint_Se…
不同路径 II 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。那么从左上…
题目
1007. Maximum Subsequence Sum (25)
时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni1, …, Nj } whe…
文章目录 Minimum Falling Path Sum II 下降路径最小和 II问题描述:分析代码DP Tag Minimum Falling Path Sum II 下降路径最小和 II
问题描述:
给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路…
代码随想录训练营第48天|198.打家劫舍,213.打家劫舍II,337.打家劫舍III 198.打家劫舍文章思路代码 213.打家劫舍III文章思路代码 337.打家劫舍III文章思路代码 总结 198.打家劫舍
文章
代码随想录|0198.打家劫舍
思路 d p [ i ] M a x ( d p [ i − …
题目
给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。
注意:你不能同时…
【LetMeFly】1289.下降路径最小和 II:通俗易懂地讲解O(n^2) O(1)的做法
力扣题目链接:https://leetcode.cn/problems/minimum-falling-path-sum-ii/
给你一个 n x n 整数矩阵 arr ,请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下…
A Safe Multi-Goal Planner for Mobile Robots in Challenging Environments
动态规划算法实现函数
1.从起点开始 连接 起点 到 最后一个TOI的所有 POI 并计算路径代价,
2.然后转入到 上一个 TOI (倒数第二个),计算新的 TOI 到…
背包问题要结束了!首先是今天的练习题,然后是多重背包的知识点,最后对这几天背包问题做一个总结!
1. 练习题
139. Word Break Given a string s and a dictionary of strings wordDict, return true if s can be segmented into…
题目描述: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径…
一、判断子序列
392. 判断子序列 - 力扣(LeetCode)
class Solution {public boolean isSubsequence(String s, String t) {int n s.length(), m t.length();int[][] f new int[m 1][26];for (int i 0; i < 26; i) {f[m][i] m;}for (int i m…
在状态压缩时,注意考虑数学上集合之间的关系:
交集:a&b
并集:a|b
对称差:a异或b
差集:a&~b
包含:a属于b时 ,a&b a or a| b b
集合与元素的关系:
全集ÿ…
题目
解法
做法有两种, O ( n 2 ) 或 O ( n k ) O(n^2)或O(nk) O(n2)或O(nk) 主要是第二种做法
设计状态: f i , j : 前 i 个数,后缀不重集的长度为 j 的方案数 f_{i,j}:前i个数,后缀不重集的长度为j的方案数 fi,j:前i个数&…
[AHOI2005] 约数研究
题目描述
科学家们在 Samuel 星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机 Samuel II 的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩,小联被允许用 Samuel II 进行数学研究。
小联最近在研究…
Every day a Leetcode
题目来源:376. 摆动序列
解法1:动态规划
约定:
某个序列被称为「上升摆动序列」,当且仅当该序列是摆动序列,且最后一个元素呈上升趋势。某个序列被称为「下降摆动序列」,当且仅当…
❓ 剑指 Offer 60. n个骰子的点数
难度:中等
把 n 个骰子扔在地上,所有骰子朝上一面的点数之和为 s 。输入 n,打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点…
P3177 [HAOI2015] 树上染色
[P3177 HAOI2015] 树上染色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 文章目录 P3177 [HAOI2015] 树上染色题目大意思路code 题目大意
有一棵 n n n 个点的树,你可以在上面把 k k k 个点染成黑色,收益为黑点两两之间…
代码:
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] pathNum new int[m][n];if(obstacleGrid[0][0]1)return 0;pathNum[0][0] 1;for(int i1;i<m;i){if(ob…
题目传送门
引
按理说,不应该想不出来,我还是太弱了,DP黑洞
解法
首先有两个性质: 1.不会删比当前 m e x mex mex 大的数 2.要删某个数一定是一删到底,直到这个数删完
状态我是真的设计不来,要积累经…
Problem - 474D - Codeforces 题意: 有白花和红花两种,把 x 朵花排成一排,要求白花必须连续 k 个一块放置,则有 cnt 种情况。给出 a 和 b,计算a到b之间的 x 对应的 cnt 总和,并且对1e97取模。
解析&#x…
题目链接 Leetcode.123 买卖股票的最佳时机 III hard 题目描述
给定一个数组,它的第 i i i 个元素是一支给定的股票在第 i i i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易&#…
给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 10^9 7 取模
示例 1:
输入:s "rabbbit", t "rabbit"
输出:3
解释:如下所示, 有 3 种可以从 s 中得…
2023牛客OI赛前集训营-提高组(第三场)C.分糖果 文章目录 2023牛客OI赛前集训营-提高组(第三场)C.分糖果题目大意做法对于 30 p t s 30pts 30pts对于 20 p t s 20pts 20pts 对于 100 p t s 100pts 100pts C-分糖果_2023牛客OI赛…
1143.最长公共子序列
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:if not text1 or not text2:return 0n=len(text1)m=len(text2)dp=[[0]*(m+1) for _ in range(n+1)]for i in range (1,n+1):for j in range(1,m+1):if text1[i-1] …
A - On and Off (atcoder.jp) (1)题意 高桥每天在S点钟打开他房间的灯,并在T点钟关灯,指示灯亮起时,日期可能会发生改变,判断是否在X点过后30分时亮着。 (2)思路 直接模拟即可。 &am…
Leetcode 2896. Apply Operations to Make Two Strings Equal 1. 解题思路2. 代码实现 题目链接:2896. Apply Operations to Make Two Strings Equal
1. 解题思路
这一题的话我一开始的思路也是贪婪算法,不过遭遇了失败,所以后来还是暴力地…
1049. 最后一块石头的重量 II
有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果…
文章目录 一、题目二、题解 一、题目
121. Best Time to Buy and Sell Stock
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a…
代码随想录算法训练营Day59|动态规划17 文章目录 代码随想录算法训练营Day59|动态规划17一、647. 回文子串二、516.最长回文子序列 一、647. 回文子串
class Solution {public int countSubstrings(String s) {boolean[][] dp new boolean[s.length()][s.length()];int res …
文章目录 一、题目二、题解 一、题目
45. Jump Game II
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words,…
Leetcode 2902. Count of Sub-Multisets With Bounded Sum 1. 解题思路2. 代码实现3. 算法优化 题目链接:2902. Count of Sub-Multisets With Bounded Sum
1. 解题思路
这一题有点惭愧,因为没有搞定,遇上了超时问题……
我的思路其实还是…
121.买卖股票的最佳时机
Python:
class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""if len(prices)0:return 0dplen(prices)*[0]minpriceint(prices[0])for i in range (1,len(prices)):minprice…
题意描述:
有 N 组物品和一个容量是 V 的背包。每组物品有若干个,同一组内的物品最多只能选一个。每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。求解将哪些物品装入背包,可使物品总体积不…
F题提交了无数遍,最后发现是三分求解的写法错了 C - Rectangle Cutting 盲猜都在xy的中心点时可以无限分割,否则不能 D - Enough Array 前缀和二分求位置 E - Common Subsequence 公共子序列求有几种组合 设 d p [ i ] [ j ] dp[i][j] dp[i][j]代表s取到…
1111-1
代码:
好难好困 梦回图论qaq
class Solution {Map<TreeNode,Integer> f new HashMap<TreeNode,Integer>();Map<TreeNode,Integer> g new HashMap<TreeNode,Integer>();public int rob(TreeNode root) {dfs(root);return Math.m…
一、题目
1、题目描述
小蓝要去健身,它可以在接下来的 1 ~ n n n 天中选择一些日子去健身。
它有 m m m 个健身计划,对于第 i i i 个健身计划,需要连续的 2 k i 2^{k_i} 2ki 天,如果成功完成,可以获得健身增益…
A. 大写字母加密(顺序或选择)
题目描述
有一种古典加密方法就是按照字母表顺序,把每个字母循环右移k位,从而转换为加密的另一个字母。例如偏移2位,即A对应C,B对应D,……X对应Z,Y对…
用Python完成:给你一个字符串 s 和一个整数 k ,请你将 s 分成 k 个 子字符串 ,使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数,表示需要修改的 最少 字符数目。注意:
如果一个字符串从左…
A 给小朋友们分糖果 I 动态规划:设 p [ k ] [ i ] p[k][i] p[k][i] 为将 i i i 个糖果分给 k k k 个小朋友的方案数,先求 p [ 2 ] [ i ] p[2][i] p[2][i] ,再求 p [ 3 ] [ n ] p[3][n] p[3][n] class Solution {
public:using ll long …
309.最佳买卖股票时机含冷冻期
思路
相对于动态规划:122.买卖股票的最佳时机II (opens new window),本题加上了一个冷冻期
在动态规划:122.买卖股票的最佳时机II (opens new window)中有两个状态,持有股票后的最多现金…
代码:
class Solution {public int findLongestChain(int[][] pairs) {Arrays.sort(pairs,new Comparator<int[]>(){Overridepublic int compare(int[] arr1,int[]arr2){return arr1[1]-arr2[1];}});int n pairs.length;int[] dp new int[n];for(int i0;i&…
题目
1049. 最后一块石头的重量 II
中等
相关标签 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <…
阶乘数码
题目描述
求 n ! n! n! 中某个数码出现的次数。
输入格式
第一行为 t ( t ≤ 10 ) t(t \leq 10) t(t≤10),表示数据组数。接下来 t t t 行,每行一个正整数 n ( n ≤ 1000 ) n(n \leq 1000) n(n≤1000) 和数码 a a a。
输出格式
对于…
题目链接
P2758 编辑距离
题目描述
设 A A A 和 B B B 是两个字符串。我们要用最少的字符操作次数,将字符串 A A A 转换为字符串 B B B。这里所说的字符操作共有三种:
删除一个字符;插入一个字符;将一个字符改为另一个字符…
UVA437 巴比伦塔 The Tower of Babylon
题面翻译
题目描述
你可能已经听说过巴比伦塔的传说。现在这个传说的许多细节已经被遗忘。所以本着本场比赛的教育性质,我们现在会告诉你整个传说:
巴比伦人有 n n n 种长方形方块,每种有无限个&a…
石子合并:
#include <iostream>using namespace std;const int N 307;int a[N];//石子
int s[N];//前缀和,保存的是前缀合的代价
int f[N][N];//状态,即代价int main()
{int n;scanf("%d",&n);for (int i 1; i < n; i ){scanf…
解析: 当任意一个数都1,这个数都会变成最大值时为sum-max-min 否则都为 sum-max-min1 只需要排序后,从第二个到最后都相等时不成立
#include<bits/stdc.h>
using namespace std;
#define int long long
const int N2e55;
int n,a[N]; …
题目 题解
class Solution:def rob(self, nums: List[int]) -> int:def dp(nums: List[int]) -> int:N len(nums)# 定义状态:dp[i]表示从第i个房屋开始偷窃,能够偷到的最高金额dp [0 for i in range(N)]for i in range(N-1, -1, -1):if i N-1:…
不同路径 II
题目描述
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。…
顾得泉:个人主页
个人专栏:《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂,年薪百万! 一、不同路径
题目链接:不同路径
题目描述 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记…
和为定值的子集数
题目描述
已知 n 个正整数,wi (1≤i≤n) 形成一个集合 W{w1,w2,...,wn},集合中的元素彼此不相同。给定某个正整数 M ,集合W中可否存在子集,该子集的所有元素之和和恰好为M,问:这样的子…
题目链接
[NOIP2007 提高组] 矩阵取数游戏
题目描述
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的 n m n \times m nm 的矩阵,矩阵中的每个元素 a i , j a_{i,j} ai,j 均为非负整数。游戏规则如下:
每次取数时须从每行各取走一…
题目 题解
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution:def rob(self, root: Optional[TreeNode]) ->…
题目链接
NOIP2015提高组第二轮 day2 - T1:Emiya 家今天的饭
题目描述
Emiya 是个擅长做菜的高中生,他共掌握 n n n 种烹饪方法,且会使用 m m m 种主要食材做菜。为了方便叙述,我们对烹饪方法从 1 ∼ n 1 \sim n 1∼n 编号&…
62.不同路径
力扣题目链接 题目描述: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。…
目录 198.打家劫舍 213.打家劫舍II 337.打家劫舍III 198.打家劫舍 题目链接:198. 打家劫舍 (1)dp[ i ] 表示经过前 i 户所偷的最高金额,且偷第 i 户; (2)dp[ i ] max( dp[ i - 2 ], dp[ i - 3 …
参考
Reinforcement Learning, Second Edition
An Introduction
By Richard S. Sutton and Andrew G. Barto动态规划 (Dynamic Programming, DP) 是一类优化方法,在给定一个用马尔可夫决策过程 (MDP) 描述的完备环境模型的情况下,其可以计算最优的策…
动态规划的核心思想是利用子问题的解来构建整个问题的解。为此,我们通常使用一个表格或数组来存储子问题的解,以便在需要时进行查找和使用。
1.最大字段和 #include <iostream>
using namespace std;
#define M 200000int main()
{int n, a[M], d…
2023每日刷题(七十二)
Leetcode—62.不同路径 超时dfs代码
class Solution {
public:int uniquePaths(int m, int n) {int starti 1, startj 1;int ans 0;function<void(int, int)> dfs [&](int i, int j) {if(i m && j n) {a…
原题链接:https://www.luogu.com.cn/problem/P1442
题目描述
在二维坐标系内有 n 个平台(定义平台是一条两端点纵坐标相同的开线段,开线段指线段两个端点不算做线段本身)和一个铁球,铁球如果下面没有物体,…
Problem: 32. 最长有效括号 文章目录 思路Code 思路
👨🏫 参考题解
Code
⏰ 时间复杂度: O ( n ) O(n) O(n) 🌎 空间复杂度: O ( n ) O(n) O(n)
class Solution {public int longestValidParentheses(String s){int n s.length();…
砝码承重
【问题描述】 你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,...,WN。请你计算一共可以称出多少种不同的正整数重量?注意砝码可以放在天平两边。【输入格式】 输入的第一行包含一个整数 N。第二行包含 N 个整数:W1,W2,W3,.…
题目描述
给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: A (表示苹果)和 . (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。
切披萨的每一刀…
题目:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径&…
1510. 石子游戏 IV - 力扣(LeetCode) 一、题目
Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。
一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石…
If every unfolding we experience takes us further along in life, then, we are truly experiencing what life is offering.如果我们在人生中体验的每一次转变都让我们在生活中走得更远,那么,我们就真正的体验到了生活想让我们体验的东西。Do not tr…
使字符串平衡的最少删除次数【LC1653】 给你一个字符串 s ,它仅包含字符 a 和 b 。 你可以删除 s 中任意数目的字符,使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ,且 s[i] b 的同时 s[j] a ,此时认为 s 是 平衡 的。 请你…
题目
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,“ACE” 是 “…
322. 零钱兑换 完全背包问题,需要注意的是数组的初始值。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount1];for(int i 0;i < amount;i){dp[i] Integer.MAX_VALUE;}dp[0] 0;for(int i 0;i < coins.length;i…
题目描述
给定长度为 n n n 的整数序列和 k k k,要求在相邻的两个数字之间插入加(‘ ’)或减(‘ − - −’)操作符(不能改变顺序),使得算术结果是k的整数倍。
例如序列为: 17 , 5 , − 21 , 15 , k 7 17, 5, -2…
给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式 第一行输入整数 n 。
接下来 n 行每行 n 个整数,其中第 i 行…
Every day a Leetcode
题目来源:2707. 字符串中的额外字符
解法1:动态规划
题目要求将字符串 s 分割成若干个互不重叠的子字符串(以下简称为子串),同时要求每个子串都必须在 dictionary 中出现。一些额外的字符可能…
给定一张 n n n 个点的带权无向图,点从 0∼ n n n−1 标号,求起点 0 到终点 n n n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n n n−1 不重不漏地经过每个点恰好一次。
输入格式 第一行输入整数 n n n。
接下来 行每行 n n n 个…
状态转移问题,一个状态的改变还会牵涉到此状态之前的状态时,很难利用简单的动态规划解决,可以考虑利用BFS队列优化,把更新过的状态存进队列中,队列空时停止 例题:2024牛客寒假集训2D-Tokitsukaze and Slash…
300.最长递增子序列 该题关键就是定义dp,dp[i]是以nums[i]为结尾的i之前包括i的最长递增子序列。 需要遍历i之前的元素和nums[i]比较大小,如果nums[i] > nums[j]那么就属于递增,就dp[i]1。
class Solution {public int lengthOfLIS(int[]…
474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1: 输入:…
题目:
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。
示例 1:
输入&#…
目录B. Vittorio Plays with LEGO Bricks(动态规划)题意:输入1:输出1:输入2:输出2:解题:代码:G. Another Wine Tasting Event题意:样例输入1输出1样例输入2输…
LeetCode 392.判断子序列 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 视频讲解https://www.bilibili.com/video/BV1tv4y1B7ym/?spm_id_from333.788&vd_sourcef98f2942b3c4cafea8907a325fc56a48文章讲解https://programmercarl.com/0392.%E5%88%A4%E6%96%A…
题目来源 63. 不同路径 II
递归
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int row obstacleGrid.length-1;int col obstacleGrid[0].length-1;return process(row,col,0,0,obstacleGrid);}private int process(int row ,int col,int i…
Leetcode 337. House Robber III
Description
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the sma…
今年比去年难好多
A. 日期统计
直接8个for,然后剪枝一下(只取2023)开头的,跑起来还是很快的,自己电脑100ms,机房1s左右 我算的答案是235,不一定对qwq
#include <bits/stdc.h>
using namespace st…
C. Parsa’s Humongous Tree Parsa has a humongous tree on n vertices.
On each vertex v he has written two integers lv and rv.
To make Parsa’s tree look even more majestic, Nima wants to assign a number av (lv≤av≤rv) to each vertex v such that the beaut…
组合总和 III leetcode216. 组合总和 III题目描述解题思路代码演示 回溯算法专题 leetcode216. 组合总和 III 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/combination-sum-iii 题目描述 找出所有相加之和为 n 的 k 个…
宣传一下算法提高课整理 <—
CSDN个人主页:更好的阅读体验 <— 本题链接(AcWing)
点这里
题目描述
在网友的国度中共有 n n n 种不同面额的货币,第 i i i 种货币的面额为 a [ i ] a[i] a[i],你可以假…
文章目录A Cat 规律C < 3 numbersF The Answer to the Ultimate Question of Life, The Universe, and Everything.L Loli, Yen-Jen, and a cool problem SAM(后缀自动机)M Kill The Tree 树的重心题目集地址
2019ICPC徐州站A Cat 规律
题目地址A Cat 题目大意:有101810^18…
583. Delete Operation for Two Strings
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 “sea”,…
New Year Garland
题意
用m种颜色的球装饰n层的圣诞树,圣诞树的第i层由 l i l_{i} li个彩球串成,且同一层相邻的球颜色不同,相邻的层之间彩球颜色的集合不同,问有多少种方案,对p取模。
分析
首先先计算每一…
给出一个长为 N N N 的整数数组 A A A 和一个整数 K K K。
请问有数组 A A A 中有多少个子数组,其元素之和为 K K K?
输入格式
第一行两个整数 N N N 和 K K K,表示数组 A A A 的大小,和给出的整数 K K K。
第二行 …
文章目录C Flippy Sequence 组合数学 分类D Magic MultiplicationE Plants vs. ZombiesF TournamentJ BooksM Function and Function题目集地址
ICPC青岛2018提交题目地址
ZOJ4058-4070C D E F J M KC Flippy Sequence 组合数学 分类
题目地址C Flippy Sequence 题目大意&…
class Solution {
public:int firstBadVersion(int n) {int left 1, right n, ans n;while(left < right){//以后尽量还是写下面这个格式的,防止INT型溢出int mid left (right - left) / 2;//如果false向左找,true向右找if(!isBadVersion(mid))l…
文章目录背包问题01 背包完全背包多重背包多重背包二进制优化分组背包混合背包背包方案数依赖背包背包方案背包问题
01 背包
for(int i 1; i < n; i )
{cin >> v >> w;for(int j m; j > v; j --)//体积从大到小,这样物品i仅使用了一次dp[j] …
121.买卖股票的最佳时机
思路:
状态定义
状态表示: 状态方程 { d p [ i ] [ 0 ] 表示第 i 天交易完后,手上没有股票时的最大利润, d p [ i ] [ 1 ] 表示第 i 天交易完后,手上持有股票时的最大利润。 状态方程 …
题目如下:
For a decimal number x with n digits (AnAn−1An−2...A2A1)(A_nA_{n-1}A_{n-2} ... A_2A_1)(AnAn−1An−2...A2A1), we define its weight as F(x)An∗2n−1An−1∗2n−2...A2∗2A1∗1.F(x) A_n * 2^{n-1} A_{n-1} * 2^{n-2} ... A_2 *…
题目如下:
Given two integers a and b, we write the numbers between a and b, inclusive, in a list. Your task is to calculate the number of occurrences of each digit. For example, if a1024a 1024a1024 and b1032b 1032b1032, the list will be 10241…
题目: 有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉碎的可能结果如下ÿ…
01
条件 : 每种物品只能拿一件 for (int i 0; i < n ; i )for (int j 0; j < W ; j )if(j < w [ i ])dp [ i 1][ j ] dp [ i ][ j ];elsedp [ i 1][ j ] max ( dp [ i ][ j ] , dp [ i ][ j - w [ i ]] v [ i ]);cout << dp[n][w] << endl;降…
原题链接 很简单的一个DP,重要的是记忆化的过程 不多说了看代码吧
代码
#include <bits/stdc.h>
using namespace std;
const int N310;
int n,m;
int g[N][N];
int f[N][N];
int dx[4]{-1,0,1,0},dy[4]{0,1,0,-1};
int dp(int i,int j)
{if(f[i][j]!-1) re…
/*给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。示例:输入: s 7, nums [2,3,1,2,4,3]输出: 2解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。*/…
题目描述 01背包问题
#include<iostream>
using namespace std;
int w[3500],val[3500];
int dp[13000];
int main(){int t,m;cin>>t>>m;for(int i1;i<t;i)cin>>w[i]>>val[i];for(int i1;i<t;i)for(int jm;j>0;j--)if(j>w[i])dp[j]…
class Solution
{
public:int maxProfit(vector<int>& prices) {if(prices.empty())return 0;//直接利用一个循环,找到最小的价钱作为买入价,并找到在此买入价下的最大利润int profit 0;int min prices[0];for(int i 1; i < prices.si…
目录
10. 正则表达式匹配 Regular Expression Matching 🌟🌟🌟
11. 盛最多水的容器 Container with most water 🌟🌟
12. 整数转罗马数字 Integer to Roman 🌟🌟
🌟 每日一练…
石子合并(弱化版)
题目描述
https://www.luogu.com.cn/problem/P1775
设有 N ( N ≤ 300 ) N(N \le 300) N(N≤300) 堆石子排成一排,其编号为 1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N 1,2,3,⋯,N。每堆石子有一定的质量 m i ( m i ≤ 1000 …
本文参考http://www.cnblogs.com/hapjin/p/5572483.html 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB,则这两个字符串的…
参考资料:《剑指Offer》
53. Maximum Subarray Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the larges…
题目: 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如&am…
文章目录F Land Overseer题目集地址
The 2021 ICPC Asia Regionals Online Contest (I)本想找机会补题的,结果这个题集不能提交了。。。F Land Overseer
题目地址F Land Overseer 思路: 注意,如果b<R时,直接从(0,0)走到(2a-R,…
CF498E Stairs and LinesCF498E Stairs and Lines 肯定是状压,而且状压的就是轮廓线,我们考虑同时状压横着和竖着的情况。然后肯定需要进行矩阵快速幂复杂度还是很高的。
但是我们考虑我们当前位置和之前位置进行转移的时候使用的是竖着的线,…
上图网址为:http://www.karaffeltut.com/NEWKaraffeltutCom/Knapsack/knapsack.html
#include <bits/stdc.h>
using namespace std;
const int maxn50;//最大物品数
const int maxw100;//最大包容量(不是包的容量) int v[maxn]{0,3,4…
问题描述
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return…
https://acs.jxnu.edu.cn/contest/22/board/challenge/A
Burglar and Matches
描述:
A burglar got into a matches warehouse and wants to steal as many matches as possible. (一个窃贼进入一个火柴仓库,偷到尽可能多的火柴࿰…
本题是一道区间型动态规划题目。
本题与 UVa 10559 Blocks 类似,可以说是该题的简化版本。令 m [ i ] m[i] m[i] 表示第 i i i 个物品,定义状态 d p [ l ] [ r ] dp[l][r] dp[l][r] 表示移除区间 [ l , r ] [l,r] [l,r] 内的可回收物品所需的最少操…
给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多…
多重背包问题朴素版(一维) 有 NN 种物品和一个容量是 VV 的背包。 第 ii 种物品最多有 sisi 件,每件体积是 vivi,价值是 wiwi。 求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。 …
打印 旋转数组Problem statement: 问题陈述: Given an array of N elements and the task is to print the elements of an array after left rotating array elements by d positions. 给定一个由N个元素组成的数组,任务是在将数组元素左旋转 d个位置后…
21安全隔离体系Here we are going to use bitwise operators to isolate rightmost one bit in the binary representation of a given number. 在这里,我们将使用按位运算符来隔离给定数字的二进制表示形式中最右边的一位 。 Problem Statement: To write a C pro…
题目描述 Today is a rainy day! Farmer John’s N (1 < N < 5,000) cows, numbered 1…N, are not particularly fond of getting wet. The cows are standing in roofless stalls arranged on a number line. The stalls span X-coordinates from 1 to M (1 < M <…
CF练习记录Codeforces Round #774 Div. 2A代码BC Factorials and Powers of Two思路代码D Weight the Tree思路代码E power Board思路代码这一套题目前两道都比较简单,直接贴上代码吧。题目集链接A
代码
#include <bits/stdc.h>
#define ll long long
using…
方法一:动态规划
class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n triangle.size();vector<vector<int>> dp(n, vector<int>(n));dp[0][0] triangle[0][0];for(int i 1; i < n; i){dp[i…
动态规划简介:
01背包问题:对于每个物品只有选和不选两种情况(与上题不同之处:物体不可分) 代码: import java.util.Arrays;
import java.util.Scanner;public class Main {/* */static int n;static int[…
覆盖墙壁 - 洛谷
/** Description: To iterate is human, to recurse divine.* Autor: Recursion* Date: 2022-05-20 21:23:11* LastEditTime: 2022-05-20 21:30:28*/
#include <bits/stdc.h>
#define LL long long
using namespace std;
const int maxn 1e6 10;
con…
题面 题解 多重背包问题:每个物品是有限个 代码
#include<bits/stdc.h>using namespace std;
const int N 1010;int n, m;
int v[N], w[N], s[N];
int f[N][N];int main() {cin >> n >> m;for (int i 1; i < n; i) cin >> v[i] >…
color#0099ff size7 face“黑体” 在解决规划的问题时,如果已经确定状态转移方程,如果确定循环的方向: 比如对于上面的状态转移方程,循环的方向应该时 i n - 1; i > 1; i– j i 1; j < n; j k i; k < j; k 按照上面…
首先声明一下,这节课基本没听懂,但是还是把课程笔记写下。
lecture19 微分动态规划 继续强化学习算法的讨论 Agenda:
课程中段我曾讲过调试learning algorithm,今天再来将强化学习的部分: The motivating example is rob…
https://acs.jxnu.edu.cn/problem/NOIOPJENGLISH18
Coins 1000ms 65536K
描述:
There are N kinds of coins. Each kind of coins has a value V and a weight W. Tony wants to go traveling. Unfortunately, he can only carry coins of which the total weig…
https://acs.jxnu.edu.cn/problem/NOIOPJENGLISH06
N Queens 1000ms 65536K
描述:
Determine the columns of N queens should be place on. Columns should be greater than 1 and less than N. Columns should be all different. Each column plus its index …
任务分配问题 背包问题Problem statement: 问题陈述: A list of n days is given to you and there are three columns. One is the day, the second one is high-effort value, and the another one is low-effort value. At a time you can pick only one either…
循环数组的单调栈(单调递减)问题,可以通过两倍数组长度取余操作模拟循环数组。
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n len(nums)stack []res [0] * nfor i in range(2*n-1, -1, -1):pos i …
[6.1 二分查找]已知有序的序列 int[] a,
整数 x
要求找到一个刚好比x稍微大一点的元素位置思路:
磁体会进行递归,但是不是所有情况都递归,比如,我们只从每次结果中选出x所在范围再进行递归,这样会减少许多操作步骤&…
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 我们令 d…
https://acs.jxnu.edu.cn/contest/24/board/challenge/A
ABC
描述:
Recently, the students of School 179 have developed a unique algorithm, which takes in a binary string ss as input. However, they soon found out that if some substring tt of ss is…
. https://acs.jxnu.edu.cn/contest/24/board/challenge/C Sorting by Swapping
描述:
Given a permutation of numbers from 1 to n, we can always get the sequence 1, 2, 3, ..., n by swapping pairs of numbers. For example, if the initial sequence is 2…
https://acs.jxnu.edu.cn/problem/ICPCJX2020J
Split Game 1000ms 131072K
描述:
Alice and Bob like to cut paper, but they only have one piece of new paper. Both of them want to use this one, but no one wants to split the new paper. Therefore, Al…
面试题14:剪绳子
给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少…
题目描述:Tino wrote a long long story. BUT! in Chinese... So I have to tell you the problem directly and discard his long long story. That is tino want to carry some oranges with "Carrying pole", and he must make two side of the Carryi…
最大子数组问题 public static int getMaxSubArray(int[] nums,int left,int right){//动态规划解法int[] D new int[nums.length]; //D[i]表示以第i个元素开头的最大的子数组和D[nums.length-1] nums[nums.length-1];int res D[nums.length - 1]; //计算的同时求最大值fo…
题面 题解 对于两个字符串,我们就可以用 f[i] [j] 来表示第一个串的前 i 个字母 和 第二串的前 j 个字母 代码
#include<bits/stdc.h>using namespace std;
const int N 1100;int n, m;
char a[N], b[N];
int f[N][N];int main() {cin >> n >> …
题面 题解 代码 #include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>using namespace std;
typedef long long ll;
const int N1e310;int n,m;
int v[N],w[N];
int f[N][N];int main(){std::ios ::syn…
原题链接
Recently Ivan the Fool decided to become smarter and study the probability theory. He thinks that he understands the subject fairly well, and so he began to behave like he already got PhD in that area.
To prove his skills, Ivan decided to demons…
原题链接
Constanze is the smartest girl in her village but she has bad eyesight.
One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce ‘c’,…
package com.seal;import java.util.Scanner;//共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。public class Main {/** 1.找到状态,由题目可知状态为两个,买了的印章个数i和集齐的印章的个数j;* 2.明确…
问题描述
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n 12, return 3 because 12 4 4 4; given n 13, return 2 because 13 4 9.
算法分析
考虑Sum a b …
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
输入格式 输入的第一行包含一个整数 N。
第二行包含 N 个整数:W1,W2,W3,⋅⋅⋅,WN。
输出…
不同的子序列问题I
作者:Grey
原文地址:
博客园:不同的子序列问题I
CSDN:不同的子序列问题I
题目链接
LeetCode 115. 不同的子序列
暴力解法
定义递归函数
int process(char[] str, char[] t, int i, int j)递归函数表示:…
357. 计算各个位数不同的数字个数
有点像规律题
n 1,有0~9这10个数字
n 2,两位数有10*9-981个可能,再加上一位数的10个数,答案是91
n 3,三位数有81*8个可能,再加上一位数和两位数
所以dp[i]&#x…
文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】 AC代码 题目
【题目描述】
一个数的序列 b i b_i bi,当 b 1 < b 2 < . . . < b S b_1<b_2<...<b_S b1<b2<...<bS的时候,我们称这个序列是上升…
CF940F Machine Learning 莫队维护区间每个数字出现的次数,维护某个出现次数是否出现过,暴力枚举mex即可,易证每次枚举最多 n \sqrt n n 次
CF375D Tree and Queries 树转链,莫队维护区间每个颜色出现的次数,如果再…
切披萨的方案数【LC1444】 给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: A (表示苹果)和 . (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。 切披萨的…
Link ST表维护gcd, 2000
题意
给出 aaa 数组,若 gcd(al,al1,...ar)r−l1gcd(a_l, a_{l1},...a_r) r - l 1gcd(al,al1,...ar)r−l1,则称区间[l,r][l,r][l,r]是boring 的。设 f(x)f(x)f(x)表示使这个数列的前x位不存在boring区间所需…
Link 线性基板子,求一个数列可以得到的第 kkk 小异或值。
int t 0;
int n;
vector<ull> b;
void insert(ull x) {for(auto i : b)x min(x, x ^ i);for(auto& i : b)i min(i, x ^ i);if(x)b.pb(x);
}
void solve() {printf("Case #%d:\n", t…
problem
学习了大佬的方法
// Decline is inevitable,
// Romance will last forever.
#include <bits/stdc.h>
using namespace std;
//#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define LL long long
#defi…
// 设f[i][j]表示有i张红牌,j张黑牌的最优策略的期望。
#include<bits/stdc.h>
using namespace std;
long long r,b;
double f[5001][5001];
int main(){scanf("%lld%lld",&r,&b);f[1][0]1;f[0][1]0;for(long long i1;i<r;i){f[i][0]i;…
F - Make Bipartite
题目描述 给出 n 1 n1 n1个点,下标是 0 0 0到 n n n,从 1 1 1到 n n n都存在一体指向0的带权无向边,边权为ar[i],同时从 i i i到 i 1 i1 i1也存在一条带权无向边,边权为 b r [ i ] br[i] br[i]&…
problem cf1800 计算两两之间的方法数,最终 anscal(a,b)∗cal(a,c)∗cal(b,c)modpans cal(a, b)*cal(a,c)*cal(b,c) mod\space panscal(a,b)∗cal(a,c)∗cal(b,c)mod p 两两之间的计算方法为依次枚举线的数量。
// Decline is inevitable,
// Romance will last f…
c语言 递归拆分数字Problem statement: Write a C Program to find the Biggest Number in an Array of integers (can be negative too) using Recursion. 问题陈述:编写一个C程序,以使用Recursion在整数数组中查找最大数(也可以为负数) 。 Algorithm:…
遗传算法 0-1背包Problem statement: 问题陈述: We have given items i1, i2 , ..., in (the item we want to put in our bag) with associated weights w1, w2, ... wn and profit values V1, V2, ... Vn. Now the problem is how we can maximize the total ben…
目录
二叉树遍历
1.Binary Tree Preorder Traversal(前序遍历)
2.Binary Tree Inorder Traversal(中序遍历)
3. Binary Tree Postorder Traversal(后序遍历)
4.Binary Tree Level Order Traversal&…
托管 非托管Today let’s introduce concepts and tools to address the use case to get a comprehensive visualization to analyse and understand resource usage on environments with many Kubernetes clusters. Our approach is specifically tailored for managed Kube…
官网
1068. Find More Coins (30)
时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a univers…
LeetCode 392- 判断子序列
题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目描述:给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除…
直接上代码
import java.io.*;public class Main {static int N100010;static int M1000010;static int n0;static int m0;static char []pnew char[N];static char []snew char[M];static int ne[]new int[N];public static void main (String[] args) throws IOExceptio…
题目描述 我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列,即可以从字符串 S 中抽出若干个字符,它们按原来的顺序组合成一个新的字符串与 T 完全一样。 给定两个字符串 S 和 T,请问最少修改 S 中的多少个字符,能使 S 包…
1. 题目描述
输入:nums [-2,1,-3,4,-1,2,1,-5,4]
输出:6 2. 解题思路
核心点是:dpi作为以数组中第 i 个元素结尾的子数组的最大和。那么就有以下关系: 3. 代码
public class ques42 {private List<Integer> ans new L…
Question
Leetcode - 面试题 17.08. Circus Tower LCCI
Train of thought
Sorting heights to be ascending order and weights to be descending order. dp[i] j represents person[i] as the bottom of tower, the tower height is amount of j, to calculate the dp[i] …
1.一和零 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。 如果 x 的所有元素也是 y 的元素࿰…
不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径?…
leetcode原题链接:最小路径和
题目描述 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。
示例 1: 输入:…
/*** author Limg* date 2023/08/11* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。* 每次你可以爬 1 或 2 个台阶。* 你有多少种不同的方法可以爬到楼顶呢?
*/#include<iostream>
using namespace std;
int climbStairs(int n);
int main()
{int n0;cin>&…
题目链接 Leetcode.174 地下城游戏 hard 题目描述
恶魔们抓住了公主并将她关在了地下城 d u n g e o n dungeon dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公…
Contest (nefu.edu.cn)
Problem:F
Time Limit:1000ms
Memory Limit:65535K
Description
一天,明明在玩纸牌游戏。
游戏规则是:一共有 n 张牌,每张牌上有一个花色 c 和一个点数 v,花色不超过 k 种。将这些牌依次放入一列牌的末…
题目链接:完全背包问题 初版(时间复杂度拉满)
#include <iostream>
#include <algorithm>using namespace std;const int N 1010;int n, m;
int v[N], w[N];
int f[N][N];int main()
{cin >> n >> m;for(int i 1; i < n; i ) cin >…
宣传一下算法提高课整理 <—
CSDN个人主页:更好的阅读体验 <— 本题链接(AcWing) 点这里
题目描述
有 N N N 件物品和一个容量是 V V V 的背包。每件物品只能使用一次。
第 i i i 件物品的体积是 v i v_i vi,价值…
题目传送门
引
题目的描述很形象,梦回童年,注意一下火柴全部都用完
解法
显然 DP ,
设计状态: f i : 用完 i 根木棒凑出的最大数 f_i:用完i根木棒凑出的最大数 fi:用完i根木棒凑出的最大数
状态转移: f i → f i c n t …
3487. 最小面积子矩阵 - AcWing题库 思路:二维矩阵前缀和,暴力枚举最小值 #include <bits/stdc.h>
using namespace std;const int M 110;
int g[M][M];int main() {int n, m, k;cin >> n >> m >> k;for (int i 1; i < n; …
继续子序列的练习!
第一题
392. Is Subsequence Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none…
1、0-1背包问题
(1)用二维数组动态规划
#include<bits/stdc.h>
using namespace std;
int m,n;
int w[50],c[50];
int dp[210][210];
int main()
{cin>>m>>n;for(int i1;i<n;i){cin>>w[i]>>c[i];}for(int i1;i<n;…
题目链接 Leetcode.118 杨辉三角 easy 题目描述
给定一个非负整数 n u m R o w s numRows numRows,生成「杨辉三角」的前 n u m R o w s numRows numRows 行。
在「杨辉三角」中,每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5 输出:…
最后一天的股票买卖问题练习!
第一题
309. Best Time to Buy and Sell Stock with Cooldown You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many…
引
对老师布置的题目稍微记录一下吧 也算对树形 D P DP DP 的巩固
T1 Ostap and Tree
题目传送门 由于有 距离 k 距离k 距离k 的限制,设计二维 d p dp dp
设计状态: f i , j : i 的子树内,离 i 最近的染色点与 i 距离为 j 且若 j <…
背包基础: 01背包:每样东西只能选一个 模板:滚动数组优化 #include <iostream>
using namespace std;const int N 1010;
int v[N], w[N]; // 存第i个物品的体积和价值
int n, m;
int f[N]; // f存状态,行表示物品ÿ…
Global Mapper是一款功能强大的地理信息系统(GIS)和地图制作软件。它由美国公司Blue Marble Geographics开发,并被广泛应用于地理数据处理、分析和可视化。
Global Mapper支持多种数据格式,包括矢量数据、栅格数据和影像数据。用…
70. 爬楼梯 class Solution {public int climbStairs(int n) {if(n <2) return n;int[] dp new int [n];dp[0] 1;dp[1] 2;for(int i 2; i< n;i){dp[i] dp[i-1] dp[i-2];}return dp[n-1];}
} 322. 零钱兑换
class Solution {public int coinChange(int[] coins, in…
题目链接 Leetcode.2522 将字符串分割成值不超过 K 的子字符串 rating : 1605 题目描述
给你一个字符串 s s s ,它每一位都是 1 1 1 到 9 9 9 之间的数字组成,同时给你一个整数 k k k 。
如果一个字符串 s s s 的分割满足以下条件,我们…
题目链接 Leetcode.2826 将三个组排序 rating : 1721 题目描述
给你一个下标从 0 0 0 开始长度为 n n n 的整数数组 n u m s nums nums 。
从 0 0 0 到 n − 1 n - 1 n−1 的数字被分为编号从 1 1 1 到 3 3 3 的三个组,数字 i i i 属于组 n u m s [ i ] …
全球半导体解决方案供应商瑞萨电21日宣布已在其Reality AI Tools?和e2 studio集成开发环境间建立接口,使设计人员能够在两个程序间无缝共享数据、项目及AI代码模块。实时数据处理模块已集成至瑞萨MCU软件开发工具套件(注),以方便…
63. 不同路径 II - 力扣(LeetCode)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”&…
1、2022
将 2022 拆分成 10 个互不相同的正整数之和, 总共有多少种拆分方法?
#include<bits/stdc.h>
using namespace std;
#define int long long
#define fp(i,a,b) for(int ia;i<b;i)
const int N1e610;
const int mod1e97;
const double eps1e-5;
typedef dou…
题面
分析:
题目最终需要达到MEX位0,也就是从最开始的MEX变成0后m的最小值,可以设 d p i dp_i dpi表示当前MEX为 i i i时,m的最小值,那么就可以根据前一个状态推出后一个状态,也就是假如当前MEX是 i i …
95. 不同的二叉搜索树 II
解题思路
遍历每一个节点查看以k为根节点的二叉搜索树储存所有左子树的根节点储存所有右子树的根节点将左子树和右子树组装起来 将根节点储存在向量中
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeN…
A 分类求和并作差 模拟 class Solution {
public:int differenceOfSums(int n, int m) {int res 0;for (int i 1; i < n; i)res i % m ! 0 ? i : -i;return res;}
};B 最小处理时间 排序:设四个 p r o c e s s o r T i m e processorTime processorTime 的元…
Problem - 431C - Codeforces 解析: #include<bits/stdc.h>
using namespace std;
#define int long long
const int mod1e97,N110;
int n,k,d,dp[N][2];
signed main(){scanf("%lld%lld%lld",&n,&k,&d);dp[0][0]1;for(int i1;i<n;…
代码:
class Solution {public int minCostClimbingStairs(int[] cost) {int n cost.length;int[] minCost new int[n1];minCost[0] 0;minCost[1] 0;for(int i2;i<n;i){minCost[i] (minCost[i-1]cost[i-1])>(minCost[i-2]cost[i-2])?(minCost[i-2]cost…
对于某类限制选 k k k个的问题,如果 f ( k ) f(k) f(k)是一个凸函数,可以二分切线的斜率,转换成无限制问题,然后根据选了几个调整斜率,使切点横坐标逼近 k k k
P2619 [国家集训队] Tree I CF125E MST Company 首先判定…
一、01背包
描述:有 N 件物品和一个容量为 V 的背包,每件物品只能使用一次 第 i 件物品的体积是 Ci,价值是 Wi 求解将哪些物品装入背包,能够在不超过背包容量的情况下使总价值最大
求解:动态规划
使用dp[i][j]表示从…
目录
242.有效的字母异位词 49.字母异位词分组 202.快乐数 219.存在重复元素Ⅱ 383.赎金信 205.同构字符串
290.单词规律 242.有效的字母异位词 题意: 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。 注意:若 s 和…
数学游戏 题目描述 Kri 喜欢玩数字游戏。 一天,他在草稿纸上写下了 ttt 对正整数 (x,y)(x,y)(x,y),并对于每一对正整数计算出了 zxygcd(x,y)z x \times y \times \gcd(x,y)zxygcd(x,y)。 可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一组的…
62. 不同路径 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径…
CSP模拟52联测14 C.天竺葵 文章目录 CSP模拟52联测14 C.天竺葵题目大意思路code 题目大意
给定两个长度为 n n n 的序列 a , b a , b a,b
需要在 a a a 序列中好到最长的序列 c c c 满足 c i 1 > b i c i c _{i 1} > b_i \times c_i ci1>bici
输出长…
A 元素和最小的山形三元组 I 前后缀操作:求出前后缀上的最小值数组,然后枚举 j j j class Solution {
public:int minimumSum(vector<int> &nums) {int n nums.size();vector<int> l(n), r(n);//l[i]min{nums[0],...,nums[i]}, r[i]mi…
文章目录 一、题目二、题解 一、题目
122.Best Time to Buy and Sell Stock II
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at …
AtCoder Beginner Contest 324
F Beautiful Path
需要一点思维的转化,一时竟然没想到。
题意
给定大小为 n n n 的有向图, m m m 条边,每条边有 b i , c i b_i,c_i bi,ci 两个属性,需要找到一条从 1 ∼ n 1\sim n 1∼n…
Portal. A. Two Regular Polygons
Portal.
正 n n n 边形中心角为 36 0 ∘ n \dfrac{360^\circ}{n} n360∘,正 m m m 边形中心角为 36 0 ∘ m \dfrac{360^\circ}{m} m360∘,若能包含显然要 ( 36 0 ∘ n ) ∣ ( 36 0 ∘ m ) (\dfrac{360^\circ…
Day 45 动态规划 part11 解题理解123188 2道题目 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV
解题理解
123
跟昨天的一题一样,只不过分了更多的状态,可以分为dp[i][0]:无操作,dp[i][1]:第一次买后持有…
题目链接:整数划分 转化成背包问题
#include <iostream>
#include <algorithm>using namespace std;const int N 1010, mod 1e9 7;int n;
int f[N];int main()
{cin >> n;f[0] 1;// i 相当于第i个物品的体积for(int i 1; i < n; i )// j …
代码随想录训练营第46天|139.单词拆分 139.单词拆分文章思路代码 总结 139.单词拆分
文章
代码随想录|0139.单词拆分
思路
外层遍历字符串长度,内层遍历单词列表,当且仅当背包长度与单词长度之间差值对应部分恰好等于当前单词时为true d p [ i ] d…
整数拆分 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k > 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。
class Solution {public int integerBreak(int n) {int[] dp new int[n 1];//正整数&#x…
定长路径计数 给一个 n n n 阶有向图,每条边的边权均为 1 1 1,然后给一个整数 k k k,你的任务是对于所有点对 ( u , v ) (u,v) (u,v) 求出从 u u u 到 v v v 长度为 k k k 的路径的数量 乘法原理 P4159 [SCOI2009] 迷路 拆点建边 P2151…
一、最长公共子序列
1143. 最长公共子序列 - 力扣(LeetCode)
class Solution {public int longestCommonSubsequence(String s1, String s2) {int n s1.length(), m s2.length();char[] cs1 s1.toCharArray(), cs2 s2.toCharArray();int[][] f n…
不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
class Solution {//testpublic int numTrees(int n) {//初始化 dp 数组int[] dp new int[n 1];//初始化…
A 子数组不同元素数目的平方和 I 枚举:枚举子数组,用集合记录当前子数组中不同元素的个数 class Solution {
public:using ll long long;int sumCounts(vector<int> &nums) {ll mod 1e9 7;int n nums.size();unordered_set<int> s;l…
动态规划第五天,加油!
第一题
1049. Last Stone Weight II You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose any two stones and smash…
开始第七天的练习!
第一题
70. Climbing Stairs You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 在刚进行动态规划的练习时候ÿ…
题目链接:最长上升子序列 II #include <iostream>
#include <algorithm>using namespace std;const int N 100010;int n;
int a[N];
// 不同长度上升子序列的结尾的最小值
int q[N];int main()
{cin >> n;for(int i 0; i < n; i ) cin >&…
题目内容 原题链接 给定一个长度为 n n n 的数组,将这个数组进行拆分成若干个连续子数组, 使得每个子数组的最大值减去最小值小于等于 s s s , 且每个子数组的长度大于等于 l e n len len 。
问最少可以拆分成多少个连续子数组࿰…
1105
代码:
class Solution {public int maxProfit(int[] prices) {int n prices.length;int[][] dp new int[n][3];dp[0][0] -prices[0];for(int i1;i<n;i){dp[i][0] Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);dp[i][1] dp[i-1][0] prices[i];dp[i][2…
A 找到冠军 I 枚举求强于其他所有队的队 class Solution {
public:int findChampion(vector<vector<int>> &grid) {int n grid.size();int res 0;for (int i 0; i < n; i) {int t 0;for (int j 0; j < n; j)if (j ! i)t grid[i][j];if (t n - 1) …
滑雪:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;const int N 310;
int n,m; //网格滑雪场的行和列
int f[N][N]; //状态转移式
int h[N][N]; //网格滑雪场
int dx[4] {-1,0,1,0};//行(上右下左)
int…
URL:https://codeforces.com/contest/1890
目录
A
Problem/题意
Thought/思路
Code/代码
B
Problem/题意
Thought/思路
Code/代码
C
Problem/题意
Thought/思路
Code/代码
D
Problem/题意
Thought/思路
Code/代码 A
Problem/题意
给出一个数组 A…
题目:
1015. 摘花生 - AcWing题库 思路:dp 代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N 110;
typedef long long ll;
int T, r, c;
int num[N][N];
ll dp[N][N];//dp…
1106
代码:
class Solution {public int maxProfit(int[] prices, int fee) {int n prices.length;int[][] dp new int[n][2];dp[0][0] -prices[0];dp[0][1] 0;for(int i1;i<n;i){dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1] Math.max…
一、最佳买卖股票时机含冷冻期
309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode)
public class Solution {public int maxProfit(int[] prices) {int len prices.length;if (len < 2) {return 0;}int[] dp new int[3];dp[0] 0;dp[1] -price…
http://cplusoj.com/d/senior/p/SS231107C
可以发现是求第 i i i 层到第 j j j 层的最大流。
同样先转成最小割,显然割点比个边优。然后我们可以利用状压dp来求。 f ( i , j , s ) f(i,j,s) f(i,j,s) 表示在第 i i i 层,还可以割 j j j 条边&#…
赛时没发挥好6题金尾(rank38),剩下很多能写的题,其中四个dp,傻眼ing The 2019 ICPC Asia Yinchuan Regional Contest
A Girls Band Party(背包)
有点迷惑的题,当时看只要 5 5 5 张…
Portal.
DP。
设 f ( i , j ) f(i,j) f(i,j) 表示前 i i i 条木板粉刷 j j j 次能正确粉刷的最大格子数, g ( i , j , k ) g(i,j,k) g(i,j,k) 表示第 i i i 条木板上粉刷 j j j 次涂了前 k k k 个格子能正确粉刷的最大格子数,用前缀和数组记录蓝…
解题步骤: 参考代码:
未优化的代码:
int n;
int V;
const int N1010;
int v[N];
int w[N];
int dp[N][N];int main()
{cin>>n>>V;for(int i1;i<n;i){cin>>v[i]>>w[i];}//第一问//第一行全是0,不用初…
参考代码:
未优化的代码:
int n;
int V;
const int N1010;
int v[N];
int w[N];
int dp[N][N];int main()
{cin>>n>>V;for(int i1;i<n;i){cin>>v[i]>>w[i];}//第一问://dp表中的第一行全是0,无需初始…
题目传送门
引
复杂度没算对导致不敢写,分析复杂度时还是多考虑势能,不然错过正解就亏了
解法
操作一可以一开始就做了 考虑状压 m a s k mask mask 是已加入序列的元素 转移枚举一段连续的区间即可 复杂度乍眼一看是 O ( n 2 2 n ) O(n^22^n) O(…
题目
给你一个整数 n ,对于 0 < i < n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n 1 的数组 ans 作为答案。
分析
通常动态规划的做题顺序,先确定dp数组dp[i],然后确定确定递推公式,再dp数…
A - QQ solver (atcoder.jp)直接按题意模拟即可。
B - Caesar Cipher (atcoder.jp)按题意模拟即可
C - Graph Isomorphism (atcoder.jp)按题意模拟即可
D - Weak Takahashi (atcoder.jp) 一个非常套路的网格dp
E - Rook Path (atcoder.jp) (1)题意 有…
题目 题解
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) -> int:# 定义状态:dp[i][j]表示s1[0:i]和s2[0:j]的最长公共子序列dp [[0 for j in range(len(text2)1)] for i in range(len(text1) 1)]# badcase: dp[i][0] 0, dp[0…
2304. 网格中的最小路径代价
给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中,从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ,且满足…
题目描述
mobiusp 创作了一首 n 个音符的乐曲,其中第 iii 个音符的音高为 ai ,但是 mobiusp 对以前的创作风格和黑历史很不满意,他希望所有音符的音高 ai 都是 1∼7 的正整数,且相邻的音高差不超过 k 。 现在他要修改若干个音符…
题目链接
题意
给定一个 n m n \times m nm 的带权矩阵,求从 ( 1 , 1 ) (1, 1) (1,1) 到 ( n , m ) (n, m) (n,m) 的两个没有交点的路径和的最大值。
分析
虽然题目限制的是同一个点不能重复经过两次,但如果一个最优解路径是有交点的,…
题目链接
这个挑战赛的 F F F是我出的,最后 zhoukangyang 爆标了。。。orzorz
记所有有颜色的边的属性集合 S S S 。
首先在外层容斥,枚举 S ∈ [ 0 , 2 w ) S\in [0,2^w) S∈[0,2w),计算被覆盖的的边中不包含 S S S 中属性,…
Problem - D - Codeforces
思路 只选两个小数计算贡献,可对序列排序,每对 ( i , j ) (i, j) (i,j) 其中 ( i < j ) (i<j) (i<j)的的贡献是 g c d ( i , j ) ⋅ ( n − j ) gcd(i, j) \cdot (n - j) gcd(i,j)⋅(n−j) 通过预处理因数欧拉反演可…
题目1: class Solution {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][4];dp[0][0]-prices[0];//持有股票dp[0][1]0;//保持卖出dp[0][2]0;//卖出当天dp[0][3]0;//冷冻期for (int i1;i<prices.length;i){dp[i][0]Math.max(dp[i-1][0]…
目录 1 基础知识2 模板3 工程化 1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1:最长上升子序列,要求时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。
解题思路:保存每个长度下的最小的结尾元素值,遍历数组元素…
动态规划十大经典问题
动态规划十大经典问题 数塔取数问题、矩阵取数问题、最大连续子段和、最长递增子序列、最长公共子序列、最长公共子串、最短编辑距离、背包问题、正整数分组、股票买卖问题。 1、数塔取数问题
// 数塔取数问题
public static int dataTowerAccess(int[]…
目录 1 基础知识2 模板3 工程化 1 基础知识
(零) 背包问题描述:有 N N N个物品,每个物品的体积是 v i v_i vi,价值是 w i w_i wi,现有容量是 V V V的背包,求这个背包能装下的物品的最大价值…
A 上一个遍历的整数 模拟 class Solution {
public:vector<int> lastVisitedIntegers(vector<string> &words) {vector<int> res;vector<int> li;for (int i 0, n words.size(); i < n;) {if (words[i] ! "prev")li.push_back(stoi…
目录 问题描述递推关系建立递推关系的思路约束条件:以 s [ k ] s[k] s[k] 结尾约束条件:以 s [ k ] s[k] s[k] 开头约束条件:增加子问题参数(前缀)约束条件:增加子问题参数(后缀)约束条件:LIS长度为k且末尾元素最小 运行实例 问…
文章目录 一、题目二、题解 一、题目
Given an integer n, break it into the sum of k positive integers, where k > 2, and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: n 2 Output: 1 Explanation: 2 1 …
62.不同路径
题目要求:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多…
2023每日刷题(五十二)
Leetcode—213.打家劫舍II 算法思路 实现代码
class Solution {
public:// 左闭右开int rob1(vector<int>& nums, int start, int end) {int n nums.size();int f0 0, f1 0, new_f 0;for(int i start; i < end…
Portal. A. Insomnia cure
Portal.
求 [ 1 , d ] [1,d] [1,d] 中能被 k , l , m , n k,l,m,n k,l,m,n 中的任意一个数整除的数的数量。
#include <bits/stdc.h>
using namespace std;
typedef long long ll;int main()
{int k,l,m,n,d;cin>>k>>l>>…
代码:
class Solution {public int maximalSquare(char[][] matrix) {int m matrix.length;int n matrix[0].length;int[][]area new int[m][n];area[0][0] matrix[0][0];int max 0;for(int i0;i<m;i){area[i][0] matrix[i][0]1? 1:0;max Math.max(area…
链接:The 2023 Guangdong Provincial Collegiate Programming Contest
有中文题面,题意就省略了。
B Base Station Construction
思路
本题参考了官方题解。
注意观察题目数据 n , m n, m n,m 的和都不超过 5 e 5 5e5 5e5,那么我们dp就…
A 找出数组中的 K-or 值 模拟 class Solution {
public:int findKOr(vector<int> &nums, int k) {vector<int> cnt(32);for (auto x: nums)for (int i 0; i < 32; i)if (x >> i & 1)cnt[i];int res 0;for (int i 0; i < 32; i)if (cnt[i] &…
2023年1月-2024年3月召开会议汇总: SIAM Symposium on Algorithm Engineering and Experiments 2024
Location: Alexandria, VA, United States
Important dates:
Conference: January 7, 2024 - January 8, 2024
Details: https://www.siam.org/conferences/cm…
第一题 简单题,就不多写了
class Solution:def findKOr(self, nums: List[int], k: int) -> int:ans [0] * 31for n in nums:for i in range(31):if 2**i & n 2**i:ans[i] 1return sum([2**i if ans[i] > k else 0 for i in range(31)])第二题 0 至少…
代码:
!!动态规划基础版完结撒花🎉
class Solution {public int numTilings(int n) {long MOD 1000000007;int[] dp new int[n1];dp[0]1;for(int i1;i<n;i){dp[i]dp[i-1]%MOD;dp[i]%MOD;if(i>2){dp[i]dp[i-2]%MOD;dp[i]…
Leetcode 2925. Maximum Score After Applying Operations on a Tree 1. 解题思路2. 代码实现 题目链接:2925. Maximum Score After Applying Operations on a Tree
1. 解题思路
这一题思路上来说还是很直接的,就是用一个深度优先遍历即可,…
题目:
895. 最长上升子序列 - AcWing题库 思路:dp 代码:
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N1010;
int f[N];//表示以i结尾的最大上升子序列…
Leetcode 2998. Minimum Number of Operations to Make X and Y Equal 1. 解题思路2. 代码实现 题目链接:10033. Minimum Number of Operations to Make X and Y Equal
1. 解题思路
这一题就是一个比较简单的动态规划的题目了。
显然,如果x小于y&…
文章目录 一、题目二、题解 一、题目
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such tha…
文章目录 一、题目二、题解 一、题目
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside t…
文章目录 一、题目二、题解 一、题目
There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member ca…
一个正整数 n 可以表示成若干个正整数之和,形如:nn1n2…nk ,其中 n1≥n2≥…≥nk,k≥1 。
我们将这样的一种表示称为正整数 n 的一种划分。
现在给定一个正整数 n ,请你求出 n 共有多少种不同的划分方法。
输入格式 共一行&…
文章目录 一、题目二、题解 一、题目
There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.
The capability of t…
绝世好题。逐步推导部分分逼近正解。
题解稍长,请耐心读完。 题目大意:给定序列 a { 1 , 2 , … n } a\lbrace1,2,\dots n\rbrace a{1,2,…n},求 n ! n! n! 种排列中 ∑ i 1 n ∑ j i n ∑ k i j 1 log 2 l o w b i t ( a i ) \s…
代码:
class Solution {public int combinationSum4(int[] nums, int target) {int n nums.length;int[] dp new int[target1];dp[0] 1;for(int i1;i<target;i){for(int num:nums){if(i-num>0){dp[i] dp[i-num];}}}return dp[target];}
}
【CSP-J 2022】上升点列 解题报告
1 题目大意
求满足某一要求的最长序列是多长。
2 题目分析
显然是最大上升子序列。
把每一个坐标存在 pair 里,排序后即可保证 x x x 单调不降,判断 y y y 是否同样单调不降即可。
设状态 d p [ i ] [ j ] dp[…
题目 题解
def knapsac(W: int, N: int, wt: List[int], val: List[int]) -> int:# 定义状态动作价值函数: dp[i][j],对于前i个物品,当前背包容量为j,最大的可装载价值dp [[0 for j in range(W1)] for i in range(N1)]# 状态动作转移for…
代码:
class Solution {public int numDecodings(String s) {int n s.length();if(s.charAt(0)0)return 0;if(n1)return 1;int[] dp new int[n1];dp[0]1;dp[1]1;for(int i2;i<n;i){if(s.charAt(i-2)1){dp[i]dp[i-2];}else if(s.charAt(i-2)2&&s.charA…
70. 爬楼梯(进阶版)
卡码网:57. 爬楼梯(opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 < m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正…
C. Palindrome Basis 题意
定义一个正整数 a a a 是回文的(没有前导 0 0 0)当且仅当: a a a 的十进制表示形式回文
给定一个正整数 n n n ,求出将 n n n 拆分成若干个回文数之和的方案数
思路
这是一个经典模型࿰…
回文是什么,回文是正着读和反着读都是一样的字符叫着回文。 如 ‘aba’,‘aa’,‘b’,这些都是回文
class Solution:def longestPalindrome(self,s: str) -> str:n len(s)dp [[False] * n for _ in range(n)]ans "…
[ABC261E] Many Operations - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Problem Statement
We have a variable X and N kinds of operations that change the value of X. Operation i is represented as a pair of integers (Ti,Ai), and is the following operati…
先看几道比较简单的题: 直接f[i][j]f[i-1][j]f[i][j-1]即可(注意有马的地方赋值为0)
下面是递推循环方式实现的AC代码:
#include<bits/stdc.h>
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
…
先补充一下背包问题: 于是,我们把每一组当成一个物品,f[k][v]表示前k组花费v的最大值。
转移方程还是max(f[k-1][v],f[k-1][v-c[i]]w[i])
伪代码(注意循环顺序):
for 所有组: for vmax.....0…
1、B站视频链接:E03 线性DP 最长上升子序列_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
int n9;
int a[101]{0,5,7,1,9,4,6,2,8,3};
int f[101];
//f[i]表示以a[i]为结尾的
//最长上升子序列的长度
int main(){int i,j,ans1;for(int i1…
一、LeetCode392. 判断子序列
题目链接:392. 判断子序列
题目描述:
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新…
文章目录 一、题目二、题解 一、题目
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols ‘’ and ‘-’ before each integer in nums and then concatenate all the integers.
For …
139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1: 输入: s “leetco…
1、B站视频链接:F06 字典树(Trie)_哔哩哔哩_bilibili
题目链接:【模板】字典树 - 洛谷 #include <bits/stdc.h>
using namespace std;
const int N100010;
int n;
char s[N];
int ch[N][26];//ch[0][2]1表示0号节点通过c边走到了节点1
int cnt[…
1. 01 背包(采用状态压缩) public static void main(String[] args) {Scanner scanner new Scanner(System.in);int M scanner.nextInt();int N scanner.nextInt();int[] value new int[N 1];int[] weight new int[N 1];int[] dp new int[M 1];…
作者推荐
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
本文涉及的基础知识点
二分查找算法合集 分组 动态规划
题目
给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。 如果对于每个满足 k < i < n-1 的下标 i ,都有…
原题链接:E. Matrix Problem 题目大意: 给出一个 n n n 行 m m m 列的 0 / 1 0/1 0/1 矩阵,再给出一些限制条件:一个长为 n n n 的数组 a a a,和一个长为 m m m 的数组 b b b 。
其中 a i a_{i} ai 表示第 …
算法沉淀——动态规划之路径问题 01.不同路径02.不同路径 II03.珠宝的最高价值04.下降路径最小和05.最小路径和06.地下城游戏 01.不同路径
题目链接:https://leetcode.cn/problems/unique-paths/
一个机器人位于一个 m x n 网格的左上角 (起始点在下图…
func max(a, b int) int { if a > b { return a } return b
}
//1049. 最后一块石头的重量 II
func lastStoneWeightII(stones []int) int { sum : 0 n : len(stones) for i : 0; i < n; i { sum stones[i] } mid : sum / 2 dp : make([]int, mid1) for i : 0; i <…
【LetMeFly】2581.统计可能的树根数目:换根DP(树形DP)
力扣题目链接:https://leetcode.cn/problems/count-number-of-possible-root-nodes/
Alice 有一棵 n 个节点的树,节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges…
Announcement
Programmed on 2024/3/2Written on 2024/3/2
题目来源
洛谷 P1415(简单版)洛谷 P2282(进阶版)
Description
给定一个仅由数字构成的字符串 s s s,用 , 将其划分为若干个正整数,使其严格…
一、题目大意
我们有N只猫,每次循环进行K次操作(N<100,K<100),每次操作可有以下三种选择:
1、g i 给第i只猫1个食物
2、e i 让第i只猫吃完它所有的食物
3、s i j 交换第i和j只猫的食物。
求出M次…
题目链接
[状态压缩动态规划] 最短Hamilton路径
题目描述
给定一张 n n n 个点的带权无向图,点从 0 0 0~ n − 1 n-1 n−1 标号,求起点 0 0 0 到终点 n − 1 n-1 n−1 的最短 H a m i l t o n Hamilton Hamilton路径。 H a m i l t o n Hamilton…
Codeforces Round 918 (Div. 4)
G. Bicycles G. Bicycles
题意:
斯拉夫的所有朋友都打算骑自行车从他们住的地方去参加一个聚会。除了斯拉维奇,他们都有一辆自行车。他们可以经过 n n n 个城市。他们都住在城市 1 1 1 ,想去参加位于城市…
518. 零钱兑换 II 先物品,后背包容量,组合数;先背包容量,后物品,排列数 感觉先物品后背包比较容易理解。对于有多少种情况这种题目,递推公式为:dp[j] dp[j-coins[i]]。
class Solution {
publ…
题目: 代码(首刷看解析 2024年2月29日): 不晓得这种超过int和long的测试案例是用来恶心谁的,用DP都没机会取模
class Solution {
public:// 动态规划const int MOD 1000000007;int numDistinct(string s, string t) {long n s.…
1、B站视频链接:E35 树形DP 积蓄程度_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
const int N200010,INF0x3f3f3f3f;
int h[N],to[N*2],w[N*2],ne[N*2],tot; //邻接表
int d[N]; //d[i]记录从i点向下流出的最大流量
int f[N]; //f…
[蓝桥杯 2020 省 AB1] 走方格
题目描述
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样,从上到下依次为第 1 1 1 至第 n n n 行,从左到右依次为第 1 1 1 至第 m m m 列,每一个点可以用行号和列号来表示。
现在有个人…
承接上一篇
升级版,别怕,上一篇弄会了,这个就是 豆芽菜✌️ https://www.acwing.com/problem/content/description/5295/
f1.递归
#include <bits/stdc.h>
// 2024-03-08 Come on !
using namespace std;
#define ll long l…
目录
力扣63. 不同路径 II
解析代码 力扣63. 不同路径 II
63. 不同路径 II
难度 中等
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(…
338.比特位计数
给你一个整数 n ,对于 0 < i < n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n 1 的数组 ans 作为答案。 class Solution {public int[] countBits(int n) {/** 思路:* 1.创建一个长度为 n…
62. 不同路径:
题目链接 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有…
目录 [NOIP2001 提高组] 数的划分题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 动态规划的解题思路Code运行结果DFSCode运行结果 [NOIP2001 提高组] 数的划分
题目描述
将整数 n n n 分成 k k k 份,且每份不能为空,任意两个方案不相…
309.最佳买卖股票时机含冷冻期
public class Solution {public int MaxProfit(int[] prices) {if(prices.Length<2){return 0;}int [,]dpnew int[prices.Length,4];dp[0,0]-prices[0];for(int i1;i<prices.Length;i){dp[i,0]Math.Max(dp[i-1,0],Math.Max(dp[i-1,3]-pric…
数字三角形 时间限制:2 sec 空间限制:256 MB 问题描述 给定一个高度为 n 的“数字三角形”,其中第 i 行(1<i<n)有 i 个数。(例子如下图所示) 初始时,你站在“数字三角形”的顶…
1049.最后一块石头的重量II
力扣题目链接(opens new window)
题目难度:中等
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < …
62.不同路径
力扣题目链接(opens new window)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。…
139.单词拆分 力扣题目链接(opens new window)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
…
问题描述:输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径,每个元素可以进行加或减的操作,从输的根节点往下一直在叶节点形成一条路径;
public void tranceTree(TreeNode node,LinkedList<…
文章目录 一、题目二、题解 一、题目
Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 109 7.
A subsequence of a string is a new string that is formed from the original string…
题目
给定三个字符串 s 1 、 s 2 、 s 3 s1、s2、s3 s1、s2、s3,请你帮忙验证 s 3 s3 s3 是否是由 s 1 s1 s1 和 s 2 s2 s2 交错 组成的。
两个字符串 s s s 和 t t t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串&…
文章目录 一、题目二、题解 一、题目
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three differen…
文章目录 一、题目二、题解 一、题目
On an n x n chessboard, a knight starts at the cell (row, column) and attempts to make exactly k moves. The rows and columns are 0-indexed, so the top-left cell is (0, 0), and the bottom-right cell is (n - 1, n - 1).
A …
Leetcode 3040. Maximum Number of Operations With the Same Score II 1. 解题思路2. 代码实现 题目链接:3040. Maximum Number of Operations With the Same Score II
1. 解题思路
这一题的话思路就是一个动态规划,显然对于每一种情况都有3种可能的…
62. 不同路径。
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径&am…
F. Divide, XOR, and Conquer 题意
给定一个非负整数数组 a a a,定义操作:
对于区间 [ l , r ] [l,r] [l,r],选择一个分界点 l ≤ k < r l \leq k < r l≤k<r,将其分成 [ l , k ] [l,k] [l,k] 和 [ k 1 , r ] [k…
这里先给出朴素做法,但是会TLE。因为这里时间复杂度最坏是N的三次方,也就是1e9比较慢,下面再给出优化的代码,
#include <iostream>
#include <algorithm>using namespace std;const int N 1010;
int n, m;
int v[N]…
作者推荐
【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数
本文涉及知识点
动态规划汇总 数学 记忆化搜索
LeetCoce964表示数字的最少运算符
给定一个正整数 x,我们将会写出一个形如 x (op1) x (op2) x (op3) x … 的表达式,其中每…
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。 每件物品的体积是 vij ,价值是 wij ,其中 i 是组号,j 是组内编号。
求解将哪些物品装入背包,可使物品总体积不超过背包容量&a…
Leetcode 3041. Maximize Consecutive Elements in an Array After Modification 1. 解题思路2. 代码实现 题目链接:3041. Maximize Consecutive Elements in an Array After Modification
1. 解题思路
这一题思路上同样就是一个动态规划,我们首先将原…
文章目录 一、题目二、题解 一、题目
You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k.
The array arr is called K-increasing if arr[i-k] < arr[i] holds for every index i, where k < i < n-1.
For exampl…
文章目录 一、题目二、题解 一、题目
You are given an array of n pairs pairs where pairs[i] [lefti, righti] and lefti < righti.
A pair p2 [c, d] follows a pair p1 [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length …
文章目录 一、题目二、题解 一、题目
Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses substring .
Example 1:
Input: s “(()” Output: 2 Explanation: The longest valid parenthe…
package main func max(a, b int) int { if a > b { return a } return b
}
背包最大重量为4。
物品为:
重量价值物品0115物品1320物品2430
每件商品都有无限个!
问背包能背的物品最大价值是多少?
func package03(weight, value []…
Leetcode 3049. Earliest Second to Mark Indices II 1. 解题思路2. 代码实现3. 算法优化 题目链接:3049. Earliest Second to Mark Indices II
1. 解题思路
这道题我看貌似难度报表,比赛的时候貌似只有36个人搞定了这道题目,然后最快的人…
1、B站视频链接:E20 背包DP 求具体方案_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
const int N1010;
int v[N],w[N];
int f[N][N],p[N][N];int main(){int n,m;cin>>n>>m;for(int i1;i<n;i)cin>>v[i]>>w[i…
1、B站视频链接:E21 线性DP 大盗阿福_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
const int N100010;
int w[N],f[N];
int main(){int n,t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i1;i<n;i…
动态规划动态规划之第 N 个泰波那契数/三步问题 动态规划LeetCode题目第 N 个泰波那契数求解1求解2(滚动数组) 三步问题求解1求解2(滚动数组) 动态规划 如果问题是由重叠的子问题构成的,那就可以用动态规划(…
647. 回文子串
题目 文章讲解 视频讲解 class Solution {public int countSubstrings(String s) {char[] chars s.toCharArray();int len chars.length;boolean[][] dp new boolean[len][len];int result 0;for (int i len - 1; i > 0; i--) {for (int j i; j < l…
322.零钱兑换
public class Solution {public int CoinChange(int[] coins, int amount) {int[] dpnew int [amount1];int maxint.MaxValue;for(int i0;i<dp.Length;i){dp[i]max;}dp[0]0;for(int i0;i<coins.Length;i){for(int jcoins[i];j<amount;j){if(dp[j-coins[…
Leetcode 3077. Maximum Strength of K Disjoint Subarrays 1. 解题思路 1. 朴素思路2. 算法优化 2. 代码实现 题目链接:3077. Maximum Strength of K Disjoint Subarrays
1. 解题思路
这道题很惭愧没有搞定,思路上出现了差错,导致一直没能…
Leetcode刷题笔记——动态规划(背包问题)篇
一、0-1 背包问题
0-1背包问题简介
有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包…
1.不同路径 II(63题)
题目描述:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finis…
[蓝桥杯 2023 省 B] 接龙数列
题目描述
对于一个长度为 K K K 的整数数列: A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,…,AK,我们称之为接龙数列当且仅当 A i A_{i} Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai−1 的末位数字…
1、B站视频链接:E44 单调队列优化DP 修剪草坪_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
typedef long long LL;
const int N1e510;
int n,k,q[N];
LL w[N],f[N],sum;int main(){cin>>n>>k; k; //for(int i1;i<n;i){ci…
一、题目描述
P8742 [蓝桥杯 2021 省 AB] 砝码称重
二、问题简析
类似 01背包,对于每个元素,可以拿(、-)或不拿。 令 d p [ i 1 ] [ j ] dp[i 1][j] dp[i1][j] 前 i 1 i 1 i1 个元素是否可以使值为 j j j。 d p [ i 1…
0-1背包,背包大小target,占用容积vec[i][0],可以带来的利益是vec[i][1] 一件物品只能取一次,先遍历物品然后遍历背包更新不同容积下最大的利益
int func(vector<vector<int>>&vec,int target){vector<int>dp(target1,…
目录 一维动态规划: 137. 爬楼梯 ①
138. 打家劫舍 ②
139. 单词拆分 ②
140. 零钱兑换 ②
141. 最长递增子序列 ②
多维动态规划:
142. 三角形最小路径和 ②
143. 最小路径和 ②
144. 不同路径 II ②
145. 最长回文子串 ②
146. 交错字符串…
func min(a, b int) int { if a < b { return a } return b
}
//583. 两个字符串的删除操作
func minDistance1(word1 string, word2 string) int { n : len(word1) h : len(word2) dp : make([][]int, n1) for i : 0; i < n; i { dp[i] make([]int, h1) //当word2为…
目录 Problem DescriptionInputOutputSample InputSample Output提示原题链接解题思路代码实现(C) Problem Description
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是&…
DFS 模板 #include<bits/stdc.h>
using namespace std;
const int N20;
int dp[N][N];
int a[N],len;
int n,m;//pos 代表当前位置 limit是当前位置是否有这个枚举范围限制int dfs(int pos,int pre,int limit){if(!pos)return 1;if(!limit&&~dp[pos][pre])return…
题目链接:392. 判断子序列
题目描述
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"…
解码方法
题目链接
思路:
状态表示 dp[i]表示到达 i 位置时,有多少种解码方法状态转移方程 根据上面的状态表示,第 i 个数字可以自己单独解码,也可以和第 i - 1 个数字一起解码,所以dp[i]就是这两种解码方式的解码方…
牛客链接 #include <bits/stdc.h>
using namespace std;
int n,V;
const int N1010;
int v[N],w[N];
int dp[N][N];
int main()
{cin>>n>>V;for(int i1;i<n;i){cin>>v[i]>>w[i];}for(int i1;i<n;i){for(int j1;j<V;j){dp[i][j]dp[i-1][…
2022.09 青少年Python等级考试(六级) 选择题部分
一、单选题(共25题,共50分) 1.以下关于Python二维数据的描述中,错误的是?( A ) A. 表格数据属于二维数据,由整数索引的数据构成 B. CSV格式每行表示—个—维数据,用英文半角逗号分隔 C. 二维数据由多条—维数据构成,…
[蓝桥杯 2023 省 B] 接龙数列
题目描述
对于一个长度为 K K K 的整数数列: A 1 , A 2 , … , A K A_{1},A_{2},\ldots,A_{K} A1,A2,…,AK,我们称之为接龙数列当且仅当 A i A_{i} Ai 的首位数字恰好等于 A i − 1 A_{i-1} Ai−1 的末位数字…
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 …
Day3462.不同路径力扣题目链接一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的…
代码源每日一题Div2
602. 01序列2
原题链接:01序列2
思路:用前缀和算出每一位的前面所有构造方法数量的和即可。
代码:
#include <bits/stdc.h>
using namespace std;
int n, k, dp[1000005], sum[1000005];
const int mod 1e9 …
多重背包问题的三种解法 转化为01背包二进制拆分优化单调队列优化 转化为01背包
题目链接:acwing4. 多重背包问题 I 题目描述 数据范围 思路: 可以转化为01背包问题求解,将s个物品都看作单独的一个物品,时间复杂度为 O ( N ∗ V ∗ S ) O(…
/* https://www.luogu.com.cn/problem/P2602 */
#include <iostream> using namespace std; // arr[i][j]: 小于等于(i1)位数的全排列中j的个数 long long arr[12][10]; // pre[i]: 小于等于(i1)位数中的前导0个数 long long pre[12];
long long pow(int n) { lon…
1.最后一块石头的重量II(1049题)
题目描述:
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那么粉…
题目: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。现在考虑网格中有障碍物。那么从左…
1、B站视频链接:E52 斜率优化DP [SDOI2012]任务安排_哔哩哔哩_bilibili
题目链接:任务安排 - 洛谷 #include <bits/stdc.h>
using namespace std;
typedef long long LL;
const int N5010;
int n,s,q[N];
LL tim[N],c[N],f[N];double slope(int …
题目叙述
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each s…
0-1背包问题详解:二维数组 文章讲解
视频讲解
0-1 背包问题:有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i],价值是 value[i],每件物品只能用一次,求解将物品装入背包里物品价值总和最大…
宣传一下算法提高课整理 <—
CSDN个人主页:更好的阅读体验 <— 本题链接(AcWing)
点这里
题目描述
有 N N N 种物品和一个容量是 V V V 的背包。
物品一共有三类:
第一类物品只能用1次(01背包࿰…
文章目录 题目描述思路代码 题目描述 思路
错位排序,可搜索引擎。复杂度太高
递推式: f [ n ] ( n − 1 ) ∗ ( f [ n − 1 ] f [ n − 2 ] ) f[n](n-1)*(f[n-1]f[n-2]) f[n](n−1)∗(f[n−1]f[n−2])
正解:打表!YYDS 1e9的数…
Leetcode 62. 不同路径题目 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路…
基础知识: 动态规划背包问题-CSDN博客 动态规划基础概念-CSDN博客 题目练习: 题目1:过河卒 题目描述 棋盘上 A 点有一个过河卒,需要走到目标 B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C 点有一个对方的马…
树的重心
题目
链接:https://www.acwing.com/problem/content/848/
给定一颗树,树中包含 n n n 个结点(编号 1 ∼ n 1 \sim n 1∼n)和 n − 1 n-1 n−1 条无向边。
请你找到树的重心,并输出将重心删除后&#x…
概述
0-1背包问题是一种经典的动态规划问题,它的基本形式是:有一个背包,容量为 C C C,有 n n n 个物品 i i i,每个物品 i i i 的重量为 w i w_i wi,价值为 v i v_i vi。现在要从这 n n n 个物品…
程序切片问题与解答
本题涉及程序切片。 a) 定义程序 s 是程序 p 相对于变量 y 的静态结束后向切片意味着什么。 [10%]
程序 p 的一个(静态的,向后的)程序切片 s 是根据切片标准 (V , n) 构建,其中 V 是一组变量名,n…
【LetMeFly】2304.网格中的最小路径代价:DP
力扣题目链接:https://leetcode.cn/problems/minimum-path-cost-in-a-grid/
给你一个下标从 0 开始的整数矩阵 grid ,矩阵大小为 m x n ,由从 0 到 m * n - 1 的不同整数组成。你可以…
题目链接
郑州轻工业大学西风校区的招新赛B题。其他题目都比较水就不写了。这个题用了线段树优化,但是不用也行(写都写了,就用了)。
题目描述有问题,“如果两相邻元素 b i , b i 1 b_i, b_{i1} bi,bi1 满足 b…
474. 一和零
题目链接:474. 一和零
题目描述
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子…
文章目录 一、题目二、题解 一、题目
A message containing letters from A-Z can be encoded into numbers using the following mapping:
‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” To decode an encoded message, all the digits must be grouped then …
今日任务
目录
完全背包理论基础
518.零钱兑换 II - Medium
377.组合总和 Ⅳ - Medium 完全背包理论基础 理论基础:代码随想录 完全背包 有N件物品和一个最多能背重量为W的背包;第i件物品的重量是weight[i],得到的价值是value[i]…
Content-Aware Unsupervised Deep Homography Estimation
内容感知的非监督深度单应矩阵估计
code
Abstract
RANSAC → learn an outlier mask (Only select reliable regions for homography estimation )
learned deep features → calculate loss
formulate a novel t…
你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。你知道存在楼层 F ,满足 0 < F < N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F…
文章目录 Maximize Grid Happiness 最大化网格幸福感问题描述:分析代码 Tag Maximize Grid Happiness 最大化网格幸福感
问题描述:
给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格,和两种类型的人:…
这场 r k 2 rk2 rk2,考的还不错,可惜考前去上了趟厕所,前面几个题罚时炸了
A
题面 水题,找到第一个 x i x_i xi使得 x i − x i − 1 ≤ d x_i-x_{i-1} \leq d xi−xi−1≤d即可
#include<bits/stdc.h>
#define re…
题目
Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.
It i…
优美的排列 II leetcode667. 优美的排列 II题目描述解题思路代码 动态规划专题 leetcode667. 优美的排列 II 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/beautiful-arrangement-ii 题目描述 给你两个整数 n 和 k &am…
583. 两个字符串的删除操作 我的代码,错误代码,只考虑到了字母出现的次数,没有考虑到两个字符串中字母出现的顺序
class Solution {public int minDistance(String word1, String word2) {int[] arr1 new int[26];int[] arr2 new int[26];…
(3) 116. 跳跃游戏 public class Solution {/*** param A: A list of integers* return: A boolean*/public boolean canJump(int[] A) {// write your code hereint len A.length;boolean[] res new boolean[len];res[0] true;for(int i 1; i <…
例1. 上楼梯 分析: 方法一:递归 import java.util.Scanner;public class Main {static int cnt0;static final int mod1000000007;/* 0 1* 1 1* 2 2* 3 4* 4 7* */public static void main(String[] args) {Scanner sc new Scanner(System.in);int n s…
leetcode62不同路径(动态规划) 题目: 一个机器人位于一个 m x n 网格的左上角 机器人每次只能向下或者向右移动一步 机器人试图达到网格的右下角 问总共有多少条不同的路径? 解法: 递归,缺点太慢了,70*30的网格我好几…
文章目录B A Funny Bipartite Graph 状压DPE Bobs ProblemG Eating PlanK Tree 树上启发式合并L Who is the Champion 签到题目集地址
ICPC2019南昌B A Funny Bipartite Graph 状压DP
题目地址B A Funny Bipartite Graph 题目大意:一个二分图,左右各有n个点&#x…
文章目录6. Z 字形变换10. 正则表达式匹配11. 盛最多水的容器15. 三数之和6. Z 字形变换 过了,但是特别好时间。
class Solution:def convert(self, s: str, n: int) -> str:if len(s) < n or n 1:return sres []left 0cnt n - 1while left < len(s):…
链接:https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
使用暴力解法,没想到竟然过了。
class NumMatrix {int[][] matrix;public NumMatrix(int[][] matrix) {this.matrix matrix;}public int sumRegion(int row1, int col1, int r…
最长递增子序列dpProblem: You are given an array of length N. You have to find the longest increasing subsequence. 问题:给您一个长度为N的数组。 您必须找到最长的递增子序列 。 Constraints: 1 < N < 10^4 限制条件: 1 < N < 10 ^…
Jimmys Bad Day题目信息输入输出测试样例样例1样例2来源解答想法题目信息
Jimmy works in an express company. His job is to deliver the packages to customers as soon as possible. He should deliver all the packages to their customers according to the orders befo…
Roping the Field题目信息输入输出测试样例提示来源解答想法题目信息
Farmer John is quite the nature artist: he often constructs large works of art on his farm. Today, FJ wants to construct a giant “field web”. FJ’s field is large convex polygon with fence…
Tri Tiling题目信息输入输出测试样例来源解答想法题目信息
In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle. 有多少种方法可以用2x1多米诺骨牌平铺3xn矩形? 下面是3x12矩形的平铺示例。
输入 …
虚树是用来优化树形dp的东西,它的转移是从一些特殊点,向根节点转移,期间它有用的转移点比较特殊。通常询问次数较多,但特殊点总和较少,就可以每次询问先建虚树再跑dp。单调栈建虚树 O ( k l o g n ) O(klogn) O(klogn)…
1049. 最后一块石头的重量 II
2021.6.8每日一题
有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x < y。那…
题目 Given a string s, find the longest palindromic subsequences length in s. You may assume that the maximum length of s is 1000.
Example 1: Input:
"bbbab"Output:
4One possible longest palindromic subsequence is "
bbbb".
Example 2…
第一个问题POJ3208启示录
The number 666 is considered to be the occult “number of the beast” and is a well used number in all major apocalypse themed blockbuster movies. However the number 666 can’t always be used in the script so numbers such as 1666 a…
class Solution:def isAdditiveNumber(self, num: str) -> bool:def check(i, j):# print("Checking", i, j)a int(num[:i1])b int(num[i1:j1])if (i > 0 and num[0] 0) or ((j>i1) and num[i1] 0):# 数字多于一位但有前导0的情况return Falsewhile Tru…
文章目录 题目【题目描述】【输入】【输出】【输入样例】【输出样例】 AC代码 题目
【题目描述】
一个旅行者有一个最多能装 M M M 公斤的背包,现在有 n n n 件物品,它们的重量分别是 W 1 , W 2 , . . . , W n W_1,…
数据结构: 邻接矩阵,邻接表
1.图的存储方式:邻接矩阵,邻接表
1.稀疏图和稠密图
2.无向图: n n n 个点,最多 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2 条边, 当 m m m 接近 n ( n − 1 ) / 2 …
62.不同路径 链接地址 class Solution {
public:int uniquePaths(int m, int n) {//初始化vector<vector<int>> dp(m, vector<int>(n, 0));for (int i 0; i < m; i) dp[i][0] 1;for (int j 0; j < n; j) dp[0][j] 1;for (int i 1; i < m; i) {…
目录
A 简单的异或
题目:
解析:
B 这是dp题吗
题目链接:https://ac.nowcoder.com/acm/contest/63602/B
解析:
D 买饼干的小Y
题目:https://ac.nowcoder.com/acm/contest/63602/D
解析:
E 不爱吃早…
此题可以使用 dp 来做~ 题目传送门
题目意思:
现在有 n n n 个箱子,每个箱子里装着 a i a_i ai 杂志。一些箱子上盖着盖板(防止被雨淋),第 i i i 个盖板只能移动到第 i − 1 i-1 i−1 个箱子上。请问如何摆放盖…
105. Construct Binary Tree from Preorder and Inorder Traversal105. Construct Binary Tree from Preorder and Inorder Traversal
题意:根据前序遍历和中序遍历来构造二叉树
我的思路
要用递归造树,要同时递归左子树和右子树,造树需要…
题目传送门
引
很有意思的计数题
解法
考虑经过操作后得到的排列的性质 性质1: 设 p r e ( i ) pre(i) pre(i):前i个位置的最大值,则不会出现超过3个的连续位置的 p r e pre pre相同 必要性: 考虑反证,若有超过 3 3 3个的连续…
题目传送门
引
大家都知道集合吧,原谅我喜欢说废话
解法
先钦定 A > B A>B A>B, 先把数排好序得到数组 a a a,考虑先解决集合 X X X的问题,
设计状态:
明显只有一维( n < 1 e 5 n<1e5 n<1e5)…
代码随想录训练营第38天|62.不同路径,63.不同路径II 62.不同路径文章思路代码 63.不同路径II文章思路代码 总结 62.不同路径
文章
代码随想录|0062.不同路径
思路 d p [ i ] [ j ] { 1 , i 0 ∧ j 0 d p [ i − 1 ] [ j ] d p [ i ] [ j − 1 ] , e l s e \b…
题目链接 Leetcode.1289 下降路径最小和 II rating : 1697 题目描述
给你一个 n x n 整数矩阵 g r i d grid grid ,请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为:从 g r i d grid grid 数组中的每一行选择一个数字ÿ…
一、题目
题目描述
在一个 n n n \times n nn 的平面上,在每一行中有一条线段,第 i i i 行的线段的左端点是 ( i , L i ) (i, L_{i}) (i,Li),右端点是 ( i , R i ) (i, R_{i}) (i,Ri)。
你从 ( 1 , 1 ) (1,1) (1,1) 点出发&#x…
● 70. 爬楼梯 (进阶)
class Solution {public int climbStairs(int n) {int[] dp new int[n1];//设置背包容量:n个int m 2;//有两个物品,注意这是一个完全背包问题dp[0] 1;//initialize
for(int i 1;i<n;i){//遍历背包f…
题目链接 Leetcode.2008 出租车的最大盈利 rating : 1872 题目描述
你驾驶出租车行驶在一条有 n n n 个地点的路上。这 n n n 个地点从近到远编号为 1 1 1 到 n n n ,你想要从 1 1 1 开到 n n n ,通过接乘客订单盈利。你只能沿着编号递增的方向前…
题目链接:滑雪 #include <cstring>
#include <algorithm>
#include <iostream>using namespace std;const int N 310;int n, m;
int h[N][N];
int f[N][N];int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};int dp(int x, int y)
{int &v f…
来到了新的一块内容:打家劫舍问题。
第一题
198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is tha…
62. 不同路径 - 力扣(LeetCode)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” …
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例 1:
输入: s "leetcode", wordDict […
参考代码:
未优化代码:
class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n coins.size();const int INF 0x3f3f3f3f;//多开一行,多开一列vector<vector<int>> dp(n 1, vector<i…
相关题目 20. 有效的括号 921. 使括号有效的最少添加 1541. 平衡括号字符串的最少插入次数 32. 最长有效括号
# 20. 有效的括号
class Solution:def isValid(self, s: str) -> bool:stack []for pare in s:if pare in ([{:stack.append(pare)if not stack or (pare ) and…
动态规划算法框架:
问题结构分析递推关系建立自底向上计算最优方案追踪
背包问题
输入: n n n个商品组成的集合 O O O,每个商品有两个属性 v i v_i vi和 p i p_i pi,分别表示体积和价格背包容量 C C C
输出:
…
236. Lowest Common Ancestor of a Binary Tree
题意:二叉树,求最近公共祖先,All Node.val are unique.
我的思路
首先把每个节点的深度得到,之后不停向上,直到val相同,存深度就用map存吧
但是它没有向…
一、买卖股票的最佳时机III
123. 买卖股票的最佳时机 III - 力扣(LeetCode)
请选一个喜欢的吧/(ㄒoㄒ)/~~123. 买卖股票的最佳时机 III - 力扣(LeetCode)
class Solution {public int maxProfit(int[] prices) {if(pricesnul…
题意描述:
有 N 种物品和一个容量是 V 的背包。物品一共有三类:第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si 次(多重背包…
URL:https://atcoder.jp/contests/abc323 目录
E
Problem/题意
Thought/思路
Code/代码
F
Problem/题意 Thought/思路
Code/代码 E
Problem/题意
有 N 首歌曲,每首歌曲时长为 Ti。每次随机播放一首歌曲,问在 X 0.5 这一时刻&#x…
CSP模拟51联测13 B.狗 文章目录 CSP模拟51联测13 B.狗题目大意题目描述输入格式输出格式样例样例 1inputoutput 思路 题目大意
题目描述
小G养了很多狗。
小G一共有 n n n\times n nn 条狗,在一个矩阵上。小G想让狗狗交朋友,一条狗狗最多只能交一个…
URL:https://atcoder.jp/contests/abc295 目录
E
Problem/题意
Thought/思路
Code/代码 E
Problem/题意
给定长度为 N 的数组 A。进行如下操作:
若 Ai 0,将 Ai 等概率地变为 1 ~ M 中的任意一个数;对 A 排序; …
URL:https://atcoder.jp/contests/abc324 目录
E
Problem/题意
Thought/思路
Code/代码
F
Problem/题意
Thought/思路
Code/代码 E
Problem/题意
给出 N 个字符串和 1 个 T 字符串,都由小写字母组成。
现在从 N 个字符串中任取 2 个拼接&…
392. 判断子序列 - 力扣(LeetCode) 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,…
Leetcode 2911. Minimum Changes to Make K Semi-palindromes 1. 解题思路2. 代码实现 题目链接:2911. Minimum Changes to Make K Semi-palindromes
1. 解题思路
这一题属实也是把我坑惨了……
坦率地说,这道题本身并没有啥难度,但是坑爹…
1. 题意
n个k面的骰子,投掷出骰子的点数之和为target的所有可能。
掷骰子等于目标和的方法数
2. 题解
动态规划,实际上相当于一个0-1背包。 令 d p [ i ] [ j ] dp[i][j] dp[i][j]为前 i i i个骰子和为j的方案数 则 d p [ i ] [ j ] ∑ t 1 k d p…
URL:https://codeforces.com/contest/1884
目录
C
Problem/题意
Thought/思路
Code/代码 C
Problem/题意
有一个长度为 M 的序列,初始值都为 0。
现在给出 N 个区间 [l, r],当选择某个区间时,可以让该区间内的数都 1。
…
数字三角形:
#include<iostream>
using namespace std;const int N510,INF0x3f3f3f3f;
int f[N][N];//存路径长度
int a[N][N];//存数字int main()
{int n;scanf("%d",&n);for(int i1;i<n;i){for(int j1;j<i;j){scanf("%d",&a…
【LetMeFly】1155.掷骰子等于目标和的方法数:动态规划
力扣题目链接:https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/
这里有 n 个一样的骰子,每个骰子上都有 k 个面,分别标号为 1 到 k 。
给定三个整数 …
Portal. C. Books Queries
Portal.
sol.
D. Boxes Packing
Portal.
把从左至右删物品转化为从右至左加物品。模拟即可。
#include <bits/stdc.h>
using namespace std;const int maxn2e55;
int a[maxn];int main()
{int n,m,k;cin>>n>>m>>k;for(…
Leetcode 2915. Length of the Longest Subsequence That Sums to Target 1. 解题思路2. 代码实现 题目链接:2915. Length of the Longest Subsequence That Sums to Target
1. 解题思路
这一题其实就是一个动态规划的题目,本身没啥难的,只…
Leetcode 2920. Maximum Points After Collecting Coins From All Nodes 1. 解题思路2. 代码实现 题目链接:2920. Maximum Points After Collecting Coins From All Nodes
1. 解题思路
这一题思路上也很直接,就是一个深度优先遍历加上一个动态规划&am…
文章目录 🎋前言🍀[第 N 个泰波那契数](https://leetcode.cn/problems/n-th-tribonacci-number/)🚩题目描述🚩算法流程🚩代码实现 🎄[使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing…
题目大意
给出一颗 n n n个节点的无根树,每个节点有一个颜色 a u a_u au,如果 a u 0 a_u0 au0则为黑色,否则为白色。
对于每个节点 u u u,选出一个包含 u u u的联通子图,设子图中白点个数为 c n t 1 cnt_1 cnt1…
1049. 最后一块石头的重量 II
题目链接:1049. 最后一块石头的重量 II
思路:本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成0-1背包问题了。与416. 分割等和子集非常相似。
动态规划五步曲&…
题目传送门
引
这种博弈问题挺经典的,第一时间就应该想到 区间 D P 区间DP 区间DP ,小小地积累一下吧
解法
设计出 D P DP DP f l . r : 考虑区间 [ l , r ] . 先手可以获得的最大差值 f_{l.r} : 考虑区间 [l,r] .先手可以获得的最大差值 fl.r:考虑区间[l,r].先手可以…
题目链接
[NOIP2015 提高组 day2 第二题] 子串
题目描述
有两个仅包含小写英文字母的字符串 A A A 和 B B B。
现在要从字符串 A A A 中取出 k k k 个互不重叠的非空子串,然后把这 k k k 个子串按照其在字符串 A A A 中出现的顺序依次连接起来得到一个新的…
题目
题面 简要题意: 你需要执行一下步骤 n n n 次来构建括号序列: ⋅ \cdot ⋅ 等概率选择一个空位(若当前有 k k k 个字符,则有 k 1 k 1 k1 个空位)。 ⋅ \cdot ⋅ 以 p p p 的概率插入字符…
Problem P25. [算法课动态规划] 整数拆分 给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k > 2 ),并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。
提示:
2 < n < 58 题目数据保证运算过程不超过 int 所能…
这道题看完就大概知道要用动态规划,然后想想如何建立动态转移方程,就很简单了,我都感觉我不是想出来的,是根据直觉应该是这样的然后边想边写就出来,以下是我的代码: class Solution {public int longestCom…
算法提高课整理
CSDN个人主页:更好的阅读体验 原题链接
题目描述
Joe觉得云朵很美,决定去山上的商店买一些云朵。
商店里有 n n n 朵云,云朵被编号为 1 , 2 , … , n 1,2,…,n 1,2,…,n,并且每朵云都有一个价值。
但是商店…
大家好,我是星恒 今天的题目竟然是一道困难题目,看着就不简单,我们的目标是:理解如何做 学一些思路! 这次题目涉及的知识:动态规划,状态压缩(位运算) 给你一个 m * n 的…
文章目录 一、题目二、题解 一、题目
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the …
Description:
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同…
139.单词拆分(需要重新写)
力扣题目链接(opens new window)
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重…
1、B站视频链接:E31 状态压缩DP 蒙德里安的梦想_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
const int N12,M1<<N;
bool st[N];//st[i]存储合并列的状态i是否合法
long long f[N][M];//f[i][j]表示摆放第i列,状态为…
01背包问题 动态规划 01背包问题 动态规划写了点代码 C#实现程序运行结果代码和程序已经上传 01背包问题 动态规划
很有意思的问题。
写了点代码 C#实现
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Ta…
1、B站视频链接:E11【模板】单调队列 滑动窗口最值_哔哩哔哩_bilibili
题目链接:滑动窗口 /【模板】单调队列 - 洛谷 #include <bits/stdc.h>
using namespace std;
const int N1000010;
int a[N],q[N];//q存的是元素的下标 int main(){int n,k;…
1、B站视频链接:E16 背包DP 分组背包_哔哩哔哩_bilibili #include <bits/stdc.h>
using namespace std;
const int N110;
int v[N][N],w[N][N],s[N];
// v[i,j]:第i组第j个物品的体积 s[i]:第i组物品的个数
int f[N][N];
// f[i,j]:前i组物品,能放…
121. 买卖股票的最佳时机
class Solution {
public:int maxProfit(vector<int>& prices) {// int res 0 ;// int low INT_MAX;// for (int i 0; i < prices.size(); i) {// low min(low, prices[i]);// res max(res, prices[i]-low);// }// return r…
1、B站视频链接:E25 状态压缩DP 小国王_哔哩哔哩_bilibili
题目链接:[SCOI2005] 互不侵犯 - 洛谷 #include <bits/stdc.h>
using namespace std;
int n,k;//棋盘行数、国王总数
int cnt;//一行合法状态的个数
int s[1<<12];//一行合法状态…
文章目录 一、题目二、题解 一、题目
There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.
In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.
Given a …
一和零
Leetcode 474
学习记录自代码随想录
要点:1.背包容量为二维,物品重量为数组元素长度,价值为1; 2.仍是01背包问题,递推公式仿照 d p [ j ] m a x ( d p [ j ] , d p [ j − w e i g h t [ i ] ] v a l u e …
LeetCode198.打家劫舍
本题较为简单,考虑一个节点时,只需要考虑偷和不偷两种情况,当不偷的情况时,取dp[n-1],这里的意思并不是决定偷n-1的节点,而是考虑n-1节点时的最大价值。
代码如下:
class Solution…
1.两重二for循环维护次大值 这里我就直接用map维护了,多了个logn复杂度还是可以的,下面是AC代码:
#include<bits/stdc.h>
using namespace std;
int n,a[1010];
map<int,int> mp;
int main(){cin>>n;int sum0;map<int,…
题目描述:
给定 V 种货币(单位:元),每种货币使用的次数不限。
不同种类的货币,面值可能是相同的。
现在,要你用这 V 种货币凑出 N 元钱,请问共有多少种不同的凑法。
输入格式&am…
[COCI2016-2017#3] Kroničan 解题记录 题意简述
有 N N N 个装有水的杯子,你需要通过从一个杯子向另一个杯子倒水,使这些杯子里面至多有 K K K 个有水,从杯子 i i i 往杯子 j j j 倒水的代价是 C i , j C_{i,j} Ci,j。 题目分析
数…
62 不同路径
一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步,机器人试图达到网格的右下角,问总共有多少条不同的路径? 分析:dp[i][j] 代表走到 (i, j) 的路径总和数 递推规律:…
比赛链接
好忙好忙好忙,慢慢补老比赛的题解了。
这场没啥算法,全是思维。有也是BFS,屎。 A. Special Characters
题意:
您将得到一个整数 n n n 。
您的任务是构建一串大写的拉丁字母。此字符串中必须正好有 n n n 个特殊字…
问题描述: 题解:
#include <bits/stdc.h>
using namespace std;
using ll long long;
const int N 1e6 9, p 1e9 7;int prefix[N],dp[N];int main()
{int n, k;cin >> n >> k;dp[0] prefix[0] 1;for(int i 1; i < n; i){i…
题目:
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1:
输入: s &qu…
前言: 这些题目是我在实验室学长讲解完基础动态规划后布置的作业。
正文: problem1 斐波那契数列: #include<bits/stdc.h>
using namespace std;
long long a[55];
int main(){a[1]1,a[2]1;for(int i3;i<50;i)a[i]a[i-1]a[i-2];int x;while(ci…
Leetcode 3098. Find the Sum of Subsequence Powers 1. 解题思路2. 代码实现 题目链接:3098. Find the Sum of Subsequence Powers
1. 解题思路
这一题思路上的话还是比较直接的,由于我们只需要求出每一个可能的power值,然后求出对应的po…
比赛链接
AB都是思维,更确切地说,A考了字符串字典序,很经典的贪心考点,B考了MEX运算。C出的还是比较好的,dp方法值得学习。D题是个不太好想的容斥,主要是变量有点多,容易搞混。 A. Entertainme…
随想录日记part38 t i m e : time: time: 2024.04.07 主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及: 打家劫舍。
198.打家劫舍213.打家劫舍II 337.打家劫舍 III 动态规划五部曲&#…
1、题目链接:[NOI1995] 石子合并 - 洛谷 #include <bits/stdc.h>
using namespace std;
const int N210;
int n,a[N],s[N];
int f[N][N];//存最小值
int g[N][N];//存最大值 int main(){memset(f,0x3f,sizeof f);//求最小初始化为无穷大 memset(g,-0x3f,size…
121. 买卖股票的最佳时机
class Solution:def maxProfit(self, prices: List[int]) -> int:dp [[0]*2 for _ in range(len(prices))]dp[0][0] -prices[0]for i in range(1,len(prices)):dp[i][0] max(dp[i-1][0],-prices[i])dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[…
随想录日记part39 t i m e : time: time: 2024.04.09 主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及: 买卖股票的最佳时机。
121. 买卖股票的最佳时机 122.买卖股票的最佳时机II 动态规…
随想录日记part31 t i m e : time: time: 2024.03.29 主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及四个方面: 理论基础 ; 斐波那契数 ;爬楼梯 ;使用最小花费爬楼梯。
理论基础 509. 斐…
1.购物单 import java.util.Scanner;public class Main {public static void main(String[] args){Scanner sc new Scanner(System.in);int N sc.nextInt();int m sc.nextInt();Goods[] goods new Goods[m];for(int i 0; i < m; i){goods[i] new Goods();}for(int i …
随想录日记part37 t i m e : time: time: 2024.04.06 主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及四个方面: 完全背包;零钱兑换 II ;组合总和 Ⅳ 和单词拆分
…
Leetcode刷题笔记——多维动态规划篇
第一题:最小路径和
Leetcode64:最小路径和:中等题 (详情点击链接见原题) 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的…