最长上升子序列问题 有一个长为n的数列a0,a1,...,a(n-1)。请求出这个序列中最长的上升子序列的长度。 上升子序列指的是对于任意的i j都满足ai aj的子序列。 1≤n≤1000 0≤ai≤1000000 输入 n=5 a={4,2,3,1,5} 输出 3(注:2,3,5) 分析 ...
LCS是Longest Common Subsequence的缩写,即最长公共子序列。 一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的...
The Triangle - POJ 1163 - Virtual Judge 题目大意 在数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。 路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。 三角形的行数大于1小于等于100,数字为 0...
钢条切割 Serling公司购买长钢条,将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出...
01背包问题 有n个重量和价值分别为wi,vi的物品,从这些物品中挑选出总重量不超过W的物品,求所有挑选方案中价值总和的最大值。 1≤n≤100 1≤wi,vi≤100 1≤W≤10000 输入: n=4 (w,v)={(2,3),(1,2),(3,4),(2,2)} W=5 输出: 7(...
题目大意 小明参加了学校的趣味运动会,其中的一个项目是:跳格子。 地上画着一些格子,每个格子里写一个字,如下所示: 从我做起振 我做起振兴 做起振兴中 起...
变态跳台阶 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 分析 关于本题,前提是n个台阶会有一次n阶的跳法。分析如下: f(1) = 1 f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一...
[华为面试题] 1分2分5分的硬币三种,组合成1角,共有多少种组合 1*x + 2*y + 5*z=10 先用最简单的暴力求解 private stat...
题目描述 有一个X*Y的网格,一个机器人只能走格点且只能向下或向右走,要从左上角走到右下角。 请设计一个算法,计算机器人有多少种走法。 给定两个正整数int x,int y,请返回机器人的走法数目,保证x+y小于等于12。 分析 先假如只有1个格子,那很明显只有一种走法,那么我们再去画 12,...