京东 上台阶 动态规划
京东 上台阶 动态规划题目描述有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或者二级,要走上m级,共有多少走法?注:规定从一级到一级有0种走法。给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100。为了防止溢出,请返回结果Mod 1000000007的值。测试样例:3 返回:2class GoUpstairs { public: int countW...
京东 上台阶 动态规划题目描述有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或者二级,要走上m级,共有多少走法?注:规定从一级到一级有0种走法。给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100。为了防止溢出,请返回结果Mod 1000000007的值。测试样例:3 返回:2class GoUpstairs { public: int countW...
网易 路灯 动态规划题目描述一条长l的笔直的街道上有n个路灯,若这条街的起点为0,终点为l,第i个路灯坐标为ai ,每盏灯可以覆盖到的最远距离为d,为了照明需求,所有灯的灯光必须覆盖整条街,但是为了省电,要使这个d最小,请找到这个最小的d。输入描述:每组数据第一行两个整数n和l(n大于0小于等于1000,l小于等于1000000000大于0)。第二行有n个整数(均大于等于0小于等于l),为每...
爱奇艺 平方串 动态规划题目描述如果一个字符串S是由两个字符串T连接而成,即S = T + T, 我们就称S叫做平方串,例如"","aabaab","xxxx"都是平方串.牛牛现在有一个字符串s,请你帮助牛牛从s中移除尽量少的字符,让剩下的字符串是一个平方串。换句话说,就是找出s的最长子序列并且这个子序列构成一个平方串。输入描述:输入一个字符串s,字符串长度length(1 ≤ lengt...
其他 最长回文子串 动态规划题目描述对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。给定字符串A以及它的长度n,请返回最长回文子串的长度。测试样例:"abc1234321ab",12 返回:7class Palindrome { public: int getLongestPalindrome(string A, int n) { ...
贝壳找房 斐波那契数列 动态规划题目描述菲波那契数列是指这样的数列:数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。给出一个正整数K,要求菲波那契数列中第k个数是多少。输入描述:输入一行,包含一个正整数k。(0<k<47)输出描述:输出一行,包含一个正整数,表示菲波那契数列中第k个数的大小示例1输入19输出4181#include<iostream> ...