zanejins

王道考研+夏令营

题解(19)

/ 注册

全部文章 / 王道考研+夏令营（共30篇）

30 STL总结来自专栏

C++ STL

2022-05-02

0 496

29 背包问题来自专栏

理论说明本节将要讨论动态规划问题中又一个十分常见，同时在机试中又是终点被考察的问题--背包问题。背包问题的变化之多让我们不容易一下子完全掌握它，根据考研机试的实际需要，我们在本节中主要讨论0-1背包、完全背包和多重背包这三类背包问题。题目来源 2008年北京大学图形学实验室计算机研究生机试真题 ...

C++ 背包

2022-05-02

0 532

28 动态规划-- 状态与状态转移方程来自专栏

理论说明在之前的LCS、递推等中，我们已经梳理了一些较为经典的动态规划问题的解法，本节将对这两种算法进行总结，并探讨解动态规划问题的统一思路。回顾两种典型问题的算法模式，我们都首先定义了一个数字量，如最长递增子序列中用dp[i]表示以序列中第i个数字结尾的最长递增子序列长度和最长公共子序列中用d...

C++ 动态规划状态迁移方程

2022-05-02

0 788

27 动态规划DP--最长公共子序列LCS 来自专栏

理论说明有两个字符串S1和S2,求一个最长的公共子串，即求字符串S3,它同时为S1和S2的子串，且要求它的长度最长，并确定这个长度。这个问题被我们称为最长公共子序列问题。与求最长递增子序列一样，我们首先将问题分割成一些子问题，我们用dp[i][j]表示S1中前i个字符与S2中前j个字符分别组成的...

C++ 动态规划 LCS

2022-05-02

0 626

26 动态规划DP--最长递增子序列（LIS）来自专栏

理论说明最长递增子序列是动态规划中最经典的问题之一，我们讨论这个问题开始，循序渐进的了解动态规划的相关知识要点。有序列{a1,a2,...,an}，我们求其最长递增子序列长度。按照递推求解的思想，我们用F[i]代表若递增序列以ai结尾时他的最长长度。当i比较小时，我们容易求解其值，如F[1]=1...

C++ 动态规划最长递增子序列

2022-05-02

0 671

25 动态规划DP--递推求解来自专栏

题目来源 2008年华中科技大学计算机保研机试真题题目描述 N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）输入说明输入包括一个整数N,(1<=N<90)。输出说明可能有多组测试数据，对于每组数据，输出当楼梯阶数是N时的上楼方式个数。样例展示 ...

动态规划 C++

2022-05-02

0 947

24 深度优先搜索（DFS）来自专栏

题目描述 The doggie found a bone in an ancient maze, which fascinated him a lot.However, when he picked it up, the maze began to shake, and the doggie cou...

C++ dfs

2022-05-01

0 402

23 递归来自专栏

理论说明本部分梳理递归，递归是一种非常常用的技巧，所谓递归即函数调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归调用。同时，为了不使这样的递归无限的发生下去，我们必须设定递归的出口，即当函数到达某种条件时停止递归。如求n阶层的递归程序如下： int f(int x) { i...

递归 bfs C++

2022-05-01

0 570

22 广度优先搜索（BFS）来自专栏

理论说明题目来源和说明九度OJ 题目描述 Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的...

C++ bfs

2022-04-30

0 449

22 枚举来自专栏

理论说明枚举是最简单也是最直白的搜索方式，它依次尝试搜索空间中所有的解，测试是否符合条件，若符合则输出答案，否则继续测试下一组解。但是在使用枚举这种相对比较暴力的算法来解题时，我们对其时间复杂度要做特别的关注。枚举问题的时间复杂度往往需要与需要枚举的情况个数有关，因为我们必须不遗不漏的枚举每一种...

C++ 枚举

2022-04-29

0 405