算法 64式 8、动态规划算法整理-python黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

我下面给你吃

1099

文章

856701

访问

+关注

分类

暂无分类

日期归档

2023-05(1)

2023-06(1)

算法 64式 8、动态规划算法整理

发布于2019-08-06 10:53 阅读(628) 评论(0) 点赞(4) 收藏(4)

1 算法思想

2 动态规划系列

类别-编号	题目	遁去的1	来源
1	N阶楼梯上楼问题 N阶楼梯上楼问题:一次可以走两阶或者一阶，问有多少种上楼方式(要求采用非递归)		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186333
2	不容易系列之一给N个网友写信，所有信全部装错信封有多少种可能的错误方式		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186349
3	最长递增子序列问题在一个已知的序列{a1,a2,...,an}中，取出若干数组组成的序列{ai1,ai2,..,aim},其中下标i1,i2,...,im保持递增，即新增数列中的各个数之间依旧保持原数列中的先后顺序，那么称新的序列为原序列的一个子序列。若在序列中，下标ix > iy时，aix > aiy，称这个子序列为原序列的一个递增子序列。		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186395
4	拦截导弹导弹系统有缺陷，后面炮弹高度<=前一发高度。计算系统能拦截多少导弹。拦截时，必须按照时间顺序，不允许先拦截后面的导弹再拦截前面的导弹。输入:每组输入两行。第一行:导弹数量k(k<=25)。第二行:k个整数，表示第k枚导弹的高度，按时间顺序，空格分隔输出:每组输出一行，包含一个整数，表示能拦截多少导弹。		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186409
5	最长公共子序列字符串S中按照先后顺序依次取出若干字符，并将它们排列成一个新的字符串，这个字符串就称为原字符串的子串。有2个字符串S1和S2，求字符串S3同时为S1和S2的子串，且要求它的长度最长，确定这个长度。		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186443
6	搬寝室 n件物品，n<2000.准备搬2k(<=n)件物品。每搬一次的疲劳度和左右手之间的重量差的平方成正比。请求出办完这2k件物品后的最低疲劳度是多少输入:每组输入数据有2行，第一行有2个数n,k(2<=2*k<=n<2000),第二行有n个整数，分别表示n件物品的重量(<2的15次方) 输出:对应每组输入数据，输出数据只有一个表示他的最少的疲劳度，每个一行.		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186477
7	Greedy Tino 有一堆柑橘，重量为0到2000，总重量不大于2000。从中取出两堆放在扁担两头，且两头重量相等，问符合条件的的每堆重量最大是多少。没有符合条件的分堆方式则输出-1 输入:第一行时t,表示t个测试用例，对每个测试用例，包含一个数字n,表名橘子数。第二行有n个数字，表明每个橘子的重量，1<=n<=100.如果是因为存在重量为0的橘子，导致扁担两边重量为0，那么应该输出0,否则输出-1		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186505
8	采药不同草药，采每一株需要一些时间，每一株有自己价值，如何让采到的价值最大。输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)，T代表总共能够用来采药的时间，M代表山洞里的草药数目。接下来的M行，每行包括两个在1到100之间(包括1和100)的整数，分别表示采摘某株草药的时间和这株草药的价值输出:在规定时间内，可以猜到的草药的最大总价值		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186535
9	Piggy-Bank 有一个储蓄罐，告知空的质量和当前重量，并给定一些钱币的价值和相应的重量，求储蓄罐中最少有多少现金。输入:包含T组测试用例。第一行。每一个测试用例包含2个整数E和F，表明空储蓄罐的重量和装满钱的重量。<=10,000g，第二行是每个测试用例，包含一个整数N(1<=N<=500)，给出了各种硬币的数量。接下来是N行，每行表示一种硬币类型，每行包括2个整数，P,W(1<=p<=50000,1<=W<=10000)，p是价值，W是重量输出: 储蓄罐中最少有多少钱		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/97750459
10	珍惜现在，感恩生活支援灾区。你有n元，市场有m种大米，每种打磨都是袋装产品，价格不等，并且只能整袋购买。你最多能采购多少公斤粮食输入:第一行1个正整数C(表示有C组测试用例)，每组测试用例的第一行时两个整数n和m(1<=n<=100,1<=m<=100)，分别表示经费的金额和大米的种类，然后是m行数据。每行包括3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。输出:输出能够购买大米最多重量，经费可以不用完		计算机考研—机试指南 https://blog.csdn.net/qingyuanluofeng/article/details/47186603
11	连续子数组的最大和: 输入一个整形数组，数组里有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)		剑指offer https://blog.csdn.net/qingyuanluofeng/article/details/39186633
12	数塔问题有形如右图的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大		算法设计与分析 https://blog.csdn.net/qingyuanluofeng/article/details/47189313
13	TSP之货郎担问题如果对于任意数目的n个城市，分别用1~n编号，则这个问题归结为在有向带权图中，寻找一条路径最短的哈密尔顿回路问题。这里，V表示城市顶点，（i,j) ∈E 表示城市之间的距离，用邻接矩阵C表示城市之间的距离。		算法设计与分析 https://blog.csdn.net/qingyuanluofeng/article/details/47189319
14	多段图的最短路径问题定义：给定有向带权图G(V,E,W)，如果把顶点集合V划分成k个不相交的子集V i ，1≤i ≤k，k≥2，使得E中的任何一条边 (u,v)，必有uЄ V i， v ∈ V i+m ，m≥1，则称这样的图为多段图。		算法设计与分析 https://blog.csdn.net/qingyuanluofeng/article/details/47189329
15	资源分配问题资源分配问题:是考虑如何把有限的资源分配给若干个工程问题。假设资源总数为 r，工程个数为n，给每个工程投入的资源不同，所得的利润也不同，要求把总数为 r 的资源分配给n个工程，以获得最大利润的分配方案		算法设计与分析 https://blog.csdn.net/qingyuanluofeng/article/details/47189335
16	最长公共子序列假定，A=a 1 a 2 …a n 是字母表∑上的一个字符序列，如果存在 ∑上的另外一个字符序列S=c 1 c 2 …c j ，使得对所有的k, k=1,2,…,j，有c k =a ik （其中，1≤ik≤n），是字符序列A的一个下标递增序列，则称字符序列S是A的子序列。如果∑={x,y,x}， ∑上的字符序列是A=xyzyxzxz，则xxx是A的一个长度为3的子序列。该子序列中的字符，对应于A的下标是1,5,7。而xzyzx是A的长度为5的子序列，对应于A的下标是1,3,4,6,7.		算法设计与分析 https://blog.csdn.net/qingyuanluofeng/article/details/47189343
17	仪器维修时间表问题一台精密仪器的工作时间为 n 个时间单位, 与仪器工作时间同步进行若干仪器维修程序. 一旦启动维修程序, 仪器必须进入维修程序. 如果只有一个维修程序启动, 则必须进入该维修程序. 如果在同一时刻有多个维修程序, 可任选进入其中的一个维修程序. 维修程序必须从头开始,不能从中间插入. 一个维修程序从第 s 个时间单位开始, 持续 t 个时间单位, 则该维修程序在第 s+t-1 个时间单位结束. 为了提高仪器使用率, 希望安排尽可能少的维修时间. 对于给定的维修程序时间表, 计算最优时间表下的维修时间. 输入数据的第 1 行有 2 个小于 10000 的正整数 n 和 k, n 表示仪器的工作时间单位, k 是维修程序数. 接下来的 k 行中, 每行有 2 个表示维修程序的整数 s 和 t, 该维修程序从第 s 个时间单位开始, 持续 t 个时间单位.		算法设计与分析 https://blog.csdn.net/qingyuanluofeng/article/details/47189359