1 算法思想
动态规划
1.1含义
把问题分解成多阶段或多个子问题，顺序求解各个子问题，最后一个子问题就是初始问题的解。
概念
阶段: 问题分成的顺序的几个环节。例如最长递增子序列中每个字符就是一个阶段。
状态: 描述问题当前状况的数字量。可以表示状态特征，例如最长递增子序列中dp[x]表示以x结尾的字符串的最长递增子序列长度，就是一个状态。
决策:从某阶段状态到下一阶段某状态的选择。例如数塔问题中取第i行第j个数有两种方案: 取第i-1行第j1个数或取第i-1行第j个数后再取第i行第j个数。
状态转移方程:数字量之间的递推关系。例如最长递增子序列中状态转移方程为:
F[i]={1, i=1
{max{1, F[j] + 1}, j < i && aj>=ai
1.2 性质
最优子结构: 问题最优解包含子问题的最优解。
无后效性:某阶段状态(数字量例如dp[x])确定后,就不受这个状态以后决策的影响。即以后不影响以前。
解释:
最优子结构: 数塔问题中，假设9->12->10->8->10是最优路径，那么12->10->8->1也是12到达最后一层的最大和
1.3适用
子问题重叠+无后效性+最优子结构的问题
为了解决子问题重叠的问题，可以采用备忘录法，用表格记录到已经计算过的状态值。
1.4通用解法
| 动态规划算法: 1 确定状态转移方程 2 初始化边界状态的值 3 设定循环来递推状态的值 4 返回目标状态的值 |
1.5经典例题讲解
0-1背包问题
不同草药，采每一株需要一些时间，每一株有自己价值，如何让采到的价值最大。
输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)，T代表总共能够用来采药的时间，M代表山洞里的草药数目。
接下来的M行，每行包括两个在1到100之间(包括1和100)的整数，分别表示采摘某株草药的时间和这株草药的价值
输出:在规定时间内，可以采到的草药的最大总价值
问题抽象:
有一个容量为V的背包，和一些物品。这些物品分别有两个属性，体积w和价值v，每种物品只有1个。
要求背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。
分析状态转移方程:
用dp[i][j]表示总体积不超过j的情况下，前i个物品能达到的最大价值。
边界状态:
dp[0][j] = 0,(0<=j<=V)
根据每个物品是否放入背包，每个状态有两个状态转移来源
若物品i放入背包，设其体积为w,价值为v,则有
dp[i][j]=dp[i-1][j-w] + v
不放入背包，则有
dp[i][j]=dp[i-1][j]
所以有:
dp[i][j]=max{ dp[i-1][j-w] + v, dp[i-1][j]}
注意: j-w的值不能为负数
| //定义背包 typedef struct List { int w;//体积 int v;//价值 }List;
int max(int a,int b) { return a > b ? a:b; }
int main(int argc,char* argv[]) { int s;//总容积 int n;//n行 int i,j; while(EOF!=scanf("%d %d",&s,&n)) { List list[101]; //int dp[101][1001]; int dp[1001];//优化 for(i = 1 ; i <= n ; i++) { scanf("%d %d",&list[i].w,&list[i].v); } //初始化边界状态的值 for(i = 0 ; i <= s ; i++) { //dp[0][i] = 0; dp[i] = 0; }
//设定循环来递推状态的值 //对于时间足够的情况，状态来源是:dp[i][j]为两者之中的最大值 for(i = 1 ; i <= n ; i++) { for(j = s; j >= list[i].w ; j--) { //dp[i][j] = max(dp[i-1][j],dp[i-1][j-list[i].w] + list[i].v); //优化:必须倒序更新每个dp[j]的值，j小于list[i].w的各dp[j]不做更新，保持原值，即等价与dp[i][j] = dp[i-1][j] dp[j] = max(dp[j],dp[j-list[i].w] + list[i].v); } /* for(j = list[i].w-1; j >= 0 ; j--) { dp[i][j] = dp[i-1][j]; } */ }
//返回目标状态的值 //printf("%d\n",dp[n][s]); printf("%d\n",dp[s]); } system("pause"); getchar(); return 0; } |
1.6动态规划与其他算法的区别
动态规划与贪心的区别:
贪心是在当前状态进行局部最优的选择，这种选择以来过去所做的选择。与贪心算法不同的是，动态规划分解的子问题往往不独立
动态规划与分治的联系:
基本思想都是将待求解问题分解成若干个子问题，先求解子问题，然后从子问题的解得到原问题的解。
1.7时间复杂度与空间复杂度
时间复杂度=状态数量*每次状态转移的时间复杂度
空间复杂度=申请的数组大小
2 动态规划系列
| 类别-编号 | 题目 | 遁去的1 | 来源 |
| 1 | N阶楼梯上楼问题 N阶楼梯上楼问题:一次可以走两阶或者一阶，问有多少种上楼方式(要求采用非递归) |
| 计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186333 |
| 2 | 不容易系列之一 给N个网友写信，所有信全部装错信封有多少种可能的错误方式 |
| 计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186349 |
| 3 | 最长递增子序列问题 在一个已知的序列{a1,a2,...,an}中，取出若干数组组成的序列{ai1,ai2,..,aim},其中下标i1,i2,...,im保持递增，即新增数列中的各个数之间依旧保持原数列中的先后顺序，那么称新的序列为原序列的一个子序列。若在序列中，下标ix > iy时，aix > aiy，称这个子序列为原序列的一个递增子序列。 |
| 计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186395 |
| 4 | 拦截导弹 导弹系统有缺陷，后面炮弹高度<=前一发高度。计算系统能拦截多少导弹。拦截时，必须按照时间顺序，不允许先拦截后面的导弹再拦截前面的导弹。 输入:每组输入两行。第一行:导弹数量k(k<=25)。第二行:k个整数，表示第k枚导弹的高度，按时间顺序，空格分隔 输出:每组输出一行，包含一个整数，表示能拦截多少导弹。 |
| 计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186409 |
| 5 | 最长公共子序列 字符串S中按照先后顺序依次取出若干字符，并将它们排列成一个新的字符串，这个字符串就称为原字符串的子串。有2个字符串S1和S2，求字符串S3同时为S1和S2的子串，且要求它的长度最长，确定这个长度。
|
| 计算机考研—机试指南 https://blog.csdn/qingyuanluofeng/article/details/47186443 |
| 6 | 搬寝室 n件物品，n<2000.准备搬2*k(<=n)件物品。每搬一次的疲劳度和左右手之间的重量差的平方成正比。请求出办完这2*k件物品后的最低疲劳度是多少 输入:每组输入数据有2行，第一行有2个数n,k(2<=2*k<=n<2000),第二行有n个整数，分别表示n件物品的重量(<2的15次方) 输出:对应每组输入数据，输出数据只有一个表示他的最少的疲劳度，每个一行. |
| 计算机考研—机试指南 https://blog.csdn/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/qingyuanluofeng/article/details/47186505 |
| 8 | 采药 不同草药，采每一株需要一些时间，每一株有自己价值，如何让采到的价值最大。 输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)，T代表总共能够用来采药的时间，M代表山洞里的草药数目。 接下来的M行，每行包括两个在1到100之间(包括1和100)的整数，分别表示采摘某株草药的时间和这株草药的价值 输出:在规定时间内，可以猜到的草药的最大总价值 |
| 计算机考研—机试指南 https://blog.csdn/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/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/qingyuanluofeng/article/details/47186603 |
| 11 | 连续子数组的最大和: 输入一个整形数组，数组里有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的 最大值。要求时间复杂度为O(n) |
| 剑指offer https://blog.csdn/qingyuanluofeng/article/details/39186633 |
| 12 | 数塔问题 有形如右图的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大 |
| 算法设计与分析 https://blog.csdn/qingyuanluofeng/article/details/47189313 |
| 13 | TSP之货郎担问题 如果对于任意数目的n个城市，分别用1~n编 号，则这个问题归结为在有向带权图中，寻找一 条路径最短的哈密尔顿回路问题。 这里，V表示城市顶点，（i,j) ∈E 表示城市之 间的距离，用邻接矩阵C表示城市之间的距离。 |
| 算法设计与分析 https://blog.csdn/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/qingyuanluofeng/article/details/47189329 |
| 15 | 资源分配问题 资源分配问题:是考虑如何把有限的资源分配给 若干个工程问题。假设资源总数为 r，工程个数为n，给每个工程投入的资源不同，所得的利润也不同，要求把总数为 r 的资源分配给n个工程，以获得最大利润的分配方案 |
| 算法设计与分析 https://blog.csdn/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/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/qingyuanluofeng/article/details/47189359 |
| 18 | 有向线段k值问题: 给定一条有向直线 L 以及 L 上的 n+1 个点 x0 < x1 < x2 < …< xn 。有向直线 L 上的每个点 xi 都有一个权 w(xi);每条有向边(xi ,xi-1) ， 也都有一个非负边长 d(xi ,xi-1)。有向直线 L 上的每个点xi 可以看作客户，其服务需求量为w(xi) 。 每条边(xi ,xi-1) 的边长 d(xi ,xi-1) 可以看作运输费用。如果在点 xi 处未设置服务机构， 则将点xi 处的服务需求沿有向边转移到点 xj 处服务机构需付出的服务转移费用为w(xi)*d(xi ,xj) 。 已知在点 x0 处设置了服务机构，求要在直线 L 上增设 k 处服务机构，使得整体服务转移费用最小的费用。 |
| 算法设计与分析 https://blog.csdn/qingyuanluofeng/article/details/50044087 |
| 20 | 饮料供货 大家对每一种饮料的满意度是知道的。微软供应部每天供应总量为V的饮料。每种饮料的单个容量都是2的方幂，比如王老吉，都是2^3 = 8升的，可乐都是 2^5 = 32升的。每种饮料也有购买量的上限。统计数据中用饮料名字，容量，数量，满意度描述每一种饮料。 如何求出保证最大满意度的购买量? |
| 编程之美 https://blog.csdn/qingyuanluofeng/article/details/39273027 |
| 21 | 求数组的子数组之和的最大值 一个由N个整数元素的数组，这个数组有很多子数组,子数组之和的最大值是什么? |
| 编程之美 https://blog.csdn/qingyuanluofeng/article/details/47187325 |
| 22 | 子数组之和的最大值(二维) |
| 编程之美 https://blog.csdn/qingyuanluofeng/article/details/47187343 |
| 23 | 求数组中最长递增子序列：（这里不要求相邻） 写一个时间复杂度尽可能低的程序，求一个一维数组(N个元素)中最长递增子序列的长度。 例如，在序列1,-1,2,-3,4,-5,6,-7中，最长递增子序列的长度为4(如1，2,4,6) |
| 编程之美 https://blog.csdn/qingyuanluofeng/article/details/47187365 |
| 24 | 数组分割 有一个无序、元素个数为2*n的正整数数组，要求:如何能把这个数组分割为元素个数为n的两个数组，并使两个子数组的和最接近? |
| 编程之美 https://blog.csdn/qingyuanluofeng/article/details/47187427 |
| 25 | 上楼的方式 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶，2阶或3阶。实现一个方法，计算小孩有多少种上楼梯的方式。 |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54233352 |
| 26 | 机器人走路的方式 设想有个机器人坐在X*Y网格的左上角，只能向右、向下移动。机器人从(0,0)到(X,Y)有多少种走法？ |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54233603 |
| 27 | 机器人走路的方式_避免禁区 设想有个机器人坐在X*Y网格的左上角，只能向右、向下移动。假设有些点为“禁区”，机器人不能踏足。设计一种算法，找出一条路径，让机器人从左上角移动到右下角。机器人从(0,0)到(X,Y)有多少种走法？ |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54233800 |
| 28 | 求堆出箱子的最大高度 给你一堆n个箱子，箱子宽Wi,高Hi,深Di。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子，实现一个方法，搭出最高的一堆箱子，箱堆的高度为每个箱子高度的总和。 |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54314545 |
| 29 | 叠罗汉问题 有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一个人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点、轻一点。已知马戏团每个人的高度和重量，请编写代码计算叠罗汉最多能叠几个人。 |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54380001 |
| 30 | 给定一个整数数组(有正数有负数)，找出总和最大的连续数列，并返回总和 |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54577889 |
| 31 | 句子分割 你写了一篇长文，却误用“查找/替换”，不慎删除了文档中所有空格、标点，大写变成小写。比如，句子"I reset the computer, It still didn't boot!"变成了"ireset the computertstilldidntboot"。你发现，只要能正确分离各个单词，加标点和调整大小写都不成问题。大部分单词在字典里都找得到，有些字符串如专有名词则找不到。 给定一个字典（一组单词），设计一个算法，找出拆分一连串单词的最佳方式。这里“最佳”的定义是，解析后无法辨识的字符序列越少越好。举个例子，字符串"jesslookedjustliketimherbrother"的最佳解析结果为"JESS looked just like TIM her brother"，总共有7个字符无法辨别，全部显示为大写，以示区别。 |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54586108 |
| 32 | 给定一个正整数和负整数组成的N*M矩阵，编写代码找出元素总和最大的子矩阵。 |
| 程序员面试金典 https://blog.csdn/qingyuanluofeng/article/details/54633084 |
| 33 | Maximum Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6. click to show more practice. More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/54970473 |
| 34 | Unique Paths 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 'Finish' in the diagram below). How many possible unique paths are there? Above is a 3 x 7 grid. How many possible unique paths are there? Note: m and n will be at most 100. |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/54980914 |
| 35 | Unique Paths II Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2. Note: m and n will be at most 100. |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/54981080 |
| 36 | Minimum Path Sum 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. 分析：动态规划。这个是要求从网格上左上角到右下角的所经过的路径上所有元素和的最小值。移动时，只能向下或者向右 进行。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/54981266 |
| 37 | Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer. |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/54986627 |
| 38 | Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2. 分析:题目对字符A到Z进行1到26的转换，现在给定数字，要求反推得原先的字母组成的不同字符串的个数 A:1,G:7,H:8,I:9,J:10,...,Z:26 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/55057157 |
| 39 | Triangle 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 bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/55224546 |
| 40 | Best Time to Buy and Sell Stock III Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 分析:至少要交易两次，求取至少交易两次下的最大值。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/55254631 |
| 41 | Word Break Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code". 分析:给定一个非空字符串，确定是否可以将字符串分割为多个字符串之后，且每个字符串都在字典中。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/55667730 |
| 42 | Word Break II 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 all such possible sentences. For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"]. A solution is ["cats and dog", "cat sand dog"]. 分析:给定一个非空字符串，确定是否可以将字符串分割为多个字符串之后，且每个字符串都在字典中。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/55668466 |
| 43 | Best Time to Buy and Sell Stock IV Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 分析:此题必须计算至多k次交易的时候获取的最大利润。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/56291342 |
| 44 | 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 that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. 分析:一个盗贼，不能连续偷两个相邻的家，问今天最多能获取的财富是多少。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/56297170 |
| 45 | House Robber II
Note: This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police. 分析:此题修改题目为环，确实可以增加获取的财富 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/56489594 |
| 46 | Maximal Square Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 4. 分析：给定一个二维矩阵，只包含0和1.找到值包含1的最大面积。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/56668234 |
| 47 | Longest Increasing Subsequence Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity? 分析:此题是求最长递增子序列。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/57419124 |
| 48 | Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day) Example: prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell] 分析:此题仍然是购买股票问题。但是抛售股票的下一天不允许买入。 求可以获得的最大利润 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/58221795 |
| 49 | Coin Change You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1) Example 2: coins = [2], amount = 3 return -1. Note: You may assume that you have an infinite number of each kind of coin. 分析:这明显是给定硬币数组，判断给定的钱能否用最少的硬币兑换。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/58651973 |
| 50 | Longest Increasing Path in a Matrix Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1: nums = [ [9,9,4], [6,6,8], [2,1,1] ] Return 4 The longest increasing path is [1, 2, 6, 9]. Example 2: nums = [ [3,4,5], [3,2,6], [2,2,1] ] Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed. 分析:题目给定一个矩阵，需要寻找到矩阵中的最长递增序列。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/59057435 |
| 51 | Integer Break Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4). Note: You may assume that n is not less than 2 and not larger than 58. 分析:将一个正整数分解为至少两个整数，然后使得分解后整数的乘积最大。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/59134848 |
| 52 | Russian Doll Envelopes You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other) Example: Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]). 分析:envelope:信封。此题是将信封不断装入另一个较大的信封中。 较小的信封必须宽度和高度都小于较大信封的宽度，高度才可以被放入。 问最多可以放入多少个信封。 这是程序员面试金典的一道题目。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/59486890 |
| 53 | Count Numbers with Unique Digits Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n. Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99]) 分析:给定一个非负整数n，输出0到10^n有多少非唯一的数字组成的数的个数，该整数 是n位数。 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/59517971 |
| 54 | Max Sum of Rectangle No Larger Than K |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/59598735 |
| 55 | Ransom Note We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I'll tell you whether the number I picked is higher or lower. However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked. Example: n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21. |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/60132523 |
| 56 | Largest Divisible Subset Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0. If there are multiple solutions, return any subset is fine. Example 1: nums: [1,2,3] Result: [1,2] (of course, [1,3] will also be ok) Example 2: nums: [1,2,4,8] Result: [1,2,4,8] 分析:给定一些列恶补相同的正整数，找到最大的子集，使其满足任意而元素(Si,Sj) 都有Si % Sj = 0 或者相反 满足这样的多个数，存在最大的数是前面一个数的倍数。次最大的数是前面的倍数,.. 也就是说所有比最大的数小的数都能被该最大数整除 |
| Leecode https://blog.csdn/qingyuanluofeng/article/details/60135291 |
| 57 | 如何求数组连续最大和 |
| Python程序员面试算法宝典 https://blog.csdn/qingyuanluofeng/article/details/92760652 |
| 58 | 如何获取最好的矩阵链相乘方法 给定一个矩阵序列，找到最有效的方式将这些矩阵相乘在一起。给定表示矩阵链 的数组p,使得第i个矩阵Ai的维数为p[i-1]*p[i]。编写一个函数 MatrixChainOrder()，该函数应该返回乘法运算所需的最小乘数。 输入: p=(40, 20, 30, 10, 30) 输出: 26000 有4个大小为40 * 20, 20 * 30, 30 * 10和10 * 30的矩阵。 假设这四个矩阵为A, B, C, D。该函数的执行方法可以使得 执行乘法运算的次数最少。 |
| Python程序员面试算法宝典 https://blog.csdn/qingyuanluofeng/article/details/93546894 |
| 59 | 如何求两个字符串的最长公共子串 找出两个字符串的最长公共子串，例如字符串"abccade"与字符串 "dgcadde"的最长公共子串为"cad" |
| python程序员面试算法宝典 https://blog.csdn/qingyuanluofeng/article/details/94298998 |
| 60 | 如何求最长递增子序列的长度 假设L=<a1, a2, ...,an>是n个不同的实数的序列，L的递增子序列是这样的一个子序列 Lin=<ak1, ak2,...,akm>，其中k1<k2<...<km且ak1<ak2<...<akm。 求最大的m值。 |
| Python程序员面试算法宝典 https://blog.csdn/qingyuanluofeng/article/details/94967031 |
| 61 | 如何求字符串的编辑距离 编辑距离又称为Levenshtein距离，是指两个字符串之间由一个转成另一个所需的 最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符、 插入一个字符、删除一个字符。请设计并实现一个算法来计算两个字符串 的编辑距离，并计算其复杂度。 在某些应用场景下，替换操作的代价比较高，假设替换操作的代价 是插入和删除的两倍，算法该如何调整。 |
| Python程序员面试算法宝典 https://blog.csdn/qingyuanluofeng/article/details/95035766 |
| 62 | 如何在二维数组中寻找最短路线 寻找一条左上角(arr[0][0])到右下角(arr[m-1][n-1])的路线，使得沿途经过 的数组中的整数的和最小。 |
| Python程序员面试算法宝典 https://blog.csdn/qingyuanluofeng/article/details/95040611 |
| 63 | 最大连续和 给出一个长度为n的序列A1,A2,...,An,求最大连续和。换句话说，要求找到1<=i <= j<=n，使得Ai+Ai+1+..+Aj尽量大 b[i] = { b[i-1] + a,b[i-1] > 0 {a,b[i-1] <0 输入: 8 1 -2 3 10 -4 7 2 -5 输出: 18(3 10 -4 7 2) |
| 算法竞赛入门经典 https://blog.csdn/qingyuanluofeng/article/details/47747103 |
| 64 | 恰好型01背包 与01背包问题的唯一不同在于：初始化状态时，除了dp[0]=0之外，其余dp[j]全为INT_MAX,而且需要判断状态是否可以得到 问题:采药。不同草药，采每一株需要一些时间，每一株有自己价值，如何让采到的价值最大。 输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)，T代表总共能够用来采药的时间，M代表山洞里的草药数目。 接下来的M行，每行包括两个在1到100之间(包括1和100)的整数，分别表示采摘某株草药的时间和这株草药的价值 输出:在规定时间内，可以猜到的草药的最大总价值 输入: 70（T采药总时间） 3(M,M行，每行是采药时间和价值) 71 100 69 1 1 2 输出: 3 |
| 算法竞赛入门经典 https://blog.csdn/qingyuanluofeng/article/details/47775925 |
| 65 | 完全01背包 完全01背包： 完全背包中每个物体可以被选择无限次，非恰好，状态dp[i][j]恰好可以由可能已经放入物品i的状态dp[i][j-goods[i].iWeight]转移而来，因此将遍历顺序该为顺序 问题:采药。不同草药，采每一株需要一些时间，每一株有自己价值，如何让采到的价值最大。 输入:第一行有两个整数T(1<=T<=1000)和M(1<=M<=100)，T代表总共能够用来采药的时间，M代表山洞里的草药数目。接下来的M行，每行包括两个在1到100之间(包括1和100)的整数，分别表示采摘某株草药的时间和这株草药的价值 输出:在规定时间内，可以猜到的草药的最大总价值 输入: 70（T采药总时间） 3(M,M行，每行是采药时间和价值) 71 100 69 1 1 2 输出: 140（2*70） |
| 算法竞赛入门经典 https://blog.csdn/qingyuanluofeng/article/details/47775951 |
| 66 | 钢条切割 钢条切割: 动态规划与分治的相同点：组合子问题求解原问题 不同点：分治的子问题不重叠，做了重复工作，动态规划保存解到表中 动态规划的特点： 1最优子结构：问题的最优解由相关子问题的最优解组合而成，子问题可以独立求解 公司出售一段长度为i英寸的钢条价格为Pi(i=1,2,...)，钢条长度为整英寸 长度i 1 2 3 4 5 6 7 8 9 10 价格Pi 1 5 8 9 10 17 17 20 24 30 给定长度为n的钢条，求使得的最大收益Rn 输入的第一行是钢条的长度n
输入: 4 输出: 10 |
| 算法导论 https://blog.csdn/qingyuanluofeng/article/details/50844819 |
| 67 | 钢条切割_动态规划的两种解法 钢条切割: 动态规划与分治的相同点：组合子问题求解原问题 不同点：分治的子问题不重叠，做了重复工作，动态规划保存解到表中 动态规划的特点： 1最优子结构：问题的最优解由相关子问题的最优解组合而成，子问题可以独立求解 动态规划的实现方式:1带备忘的自顶向下，2自底向上 1带备忘的自顶向下：递归中保存子问题的解，需要子问题的解时，首先检查是否已经保存过此解，如果是直接返回保存的值 2自底向上：定义子问题的规模，将子问题按照规模排序，按从小到大的顺序求解，求解子问题时，该子问题所依赖的更小的子问题已经保存 两个方法的区别： 自顶向下递归 自底向上无需递归，设置初始值，用两层循环: 1<= i <= n, 1<= j <= i , 用R[i] = max(R[i] , P[j] + R[i - j] ) 公司出售一段长度为i英寸的钢条价格为Pi(i=1,2,...)，钢条长度为整英寸 长度i 1 2 3 4 5 6 7 8 9 10 价格Pi 1 5 8 9 10 17 17 20 24 30 给定长度为n的钢条，求使得的最大收益Rn 输入的第一行是钢条的长度n 输入: 4 输出: 10 |
| 算法导论 https://blog.csdn/qingyuanluofeng/article/details/50846382 |
| 68 | 矩阵链乘法 给定一个n个矩阵的序列<A1,A2,...,An>,矩阵Ai的规模为Pi-1*Pi(1<=i<=n),计算乘积A1*A2*...*An 设Ai,j表示AiAi+1...Aj乘积的结果矩阵 设m[i,j]表示计算矩阵Ai,j乘法次数最小值 那么我们需要求的结果就是m[1,n] 设AiAi+1...Aj的最优括号方案的分割点在矩阵Ak和Ak+1之间，其中i<=k<j。 那么m[i,j]等于计算Ai,k和Ak+1,j的代价加上两者相乘的代价的最小值 设矩阵Ai的大小为Pi-1*Pi,那么Ai,k与Ak+1,j相乘的代价是Pi-1PiPj 其中k属于[i,j-1] 当m[i,i]时，表示只有一个矩阵，所以相乘的次数为0 m[i,j]= { 0 , i = j { min i<=k<j { m[i,k] + m[k+1, j] + Pi-1*Pk*Pj } , i < j 我们用s[i,j]保存AiAi+1...Aj的最优分割点k 采用自底向上的方法，应该按照长度顺序求解矩阵链括号化问题 输入第一行的第一个数n为矩阵的个数，第二行有n+1个数，分别为n个矩阵各自的行数+最后第n个矩阵的列数 输出最小乘法次数 输入: 6 30 35 15 5 10 20 25 输出: 15125 ((A1(A2A3))((A4A5)A6)) |
| 算法导论 https://blog.csdn/qingyuanluofeng/article/details/50848689 |
| 69 | 最优二叉搜索树 最优二叉搜索树:给定一个n个不同关键字的已经排序的序列K=<k1,k2,...,kn>(因此k1<k2<...<kn),希望用这些关键字构造一颗二叉搜索树。 对每个关键字ki,都有一个概率pi表示其搜索频率。有些要搜索的值可能不在K中，因此我们还有n+1个“伪关键字”do,d1,d2,...,dn表示不 在K中的值。d0表示所有小于k1的值，dn表示所有大于kn的值，对i=1,2,...,n-1,伪关键字di表示所有在ki和ki+1之间的值。对于每个伪关 键字di，也都有一个概率pi表示对应的搜索频率。下图显示了n=5个关键字的集合构造的两颗二叉搜索树。每个关键字ki是一个内部结点， 而每个关键字di是一个叶结点。每次搜索要么成功(找到某个关键字ki)，要么失败(找到某个伪关键字di)，因此有如下公式: i属于[1,n] pi的和 + i属于[0,n] qi的和 = 1 关键字ki的两个伪关键字为di-1,di k2 k1 k4 d0 d1 k3 k5 d2 d3 d4 d5 输出最优二叉搜索树的期望搜索代价 输入: 5 0.15 0.1 0.05 0.1 0.2 0.05 0.1 0.05 0.05 0.05 0.1 输出: 2.75 |
| 算法导论 https://blog.csdn/qingyuanluofeng/article/details/50927159 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
参考:
[1]计算机考研--机试指南,王道论坛 组编
[2]剑指offer
[3]算法设计与分析
[4]编程之美
[5]程序员面试金典
[6]leecode
[7]Python程序员面试算法宝典
[8]刘汝佳算法竞赛入门经典
[9]算法导论
[10]编程珠玑
更多推荐
算法 64式 8、动态规划算法整理
发布评论