
动态规划
动态规划为什么重要? 从面试的角度看,动态规划是正规算法面试中无论如何都逃不掉的必考题。 其实最主要的原因就是动态规划非常适合面试,因为动态规划没办法「背」。 我们很多求职者其实是通过背题来面试的,而之前这个做法屡试不爽,什么翻转二叉树、翻转链表,快排、归并、冒泡一顿背,基本上也能在面试中浑水摸鱼过去,其实这哪是考算法能力、算法思维,这就是考谁的备战态度好,愿意花时间去背题而已,把连背都懒得背的筛出去就完事了。 但是随着互联网遇冷,人才供给进一步过热,背题的人越来越多,面试的门槛被增加了,因此这个时候需要一种非常考验算法思维、变化多端而且容易设计的题目类型,动态规划就完美符合这个要求。 比如 LeetCode 中有1261道算法类题目,其中动态规划题目占据了近200道,动态规划能占据总题目的 1/6 的比例,可见其火热程度。 更重要的是,动态规划的题目难度以中高难度为主 所以,既然我们已经知道这是算法面试的必考题了,我们怎么准备都不为过。 什么是动态规划 动态规划(Dynamic programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 态规划与分治方法类似,都是通过组合子问题的解来来求解原问题的。再来了解一下什么是分治方法,以及这两者之间的差别,分治方法将问题划分为互不相交的子问题,递归的求解子问题,再将它们的解组合起来,求出原问题的解。而动态规划与之相反,动态规划应用与子问题重叠的情况,即不同的子问题具有公共的子子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。在这种情况下,分治方法会做许多不必要的工作,他会反复求解那些公共子子问题。而动态规划对于每一个子子问题只求解一次,将其解保存在一个表格里面,从而无需每次求解一个子子问题时都重新计算,避免了不必要的计算工作。 动态规划题目的特点 从「钱」讲起 我们可以算一下,按照贪心算法的策略,我们先拿出3个最大面值的7,再拿出一个面值5然后就没有办法继续了。 这里就有问题了,贪心算法的弊端在这种特殊面值钱币面前展露无疑,原因就在于「只顾眼前,无大局观」,在先拿出最大的 7 面值的硬币后就彻底把周旋余地堵死了,因为剩下的 21 要想凑足付出的代价是非常高的,我们需要依次拿出4个面值为2的硬币。 改进计算策略 那么既然贪心算法已经不适用于这种场景了,我们应该如何改变计算策略呢? 当我们面试过程中遇到这种问题时,如果一时没有思路,也要想到一种万能算法–暴力破解。 我们分析一下上述题目,它的问题其实是「给定一组面额的硬币,我们用现有的币值凑出27最少需要多少个币」。 那么假设最后一个硬币为a[k]的话,那么剩下27 - a[k],这个时候问题又变成了,我们凑出 27 - a[k]最少需要多少个币 问题可以不断被分解为「我们用现有的币值凑出 n 最少需要多少个币」,比如我们用 f(n) 函数代表 「凑出 n 最少需要多少个币」. 把「原有的大问题逐渐分解成类似的但是规模更小的子问题」这就是最优子结构,我们可以通过自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。 这个时候我们分别假设 2、5、7 三种面值的币分别为最后一个硬币的情况: 最后一枚硬币的面额为 7: min = f(20) + 1 最后一枚硬币的面额为 5: min = f(22) + 1 最后一枚硬币的面额为 2: min = f(25) + 1 这个时候大家发现问题所在了吗?最少找零 min 与 f(20)、f(22)、f(25) 三个函数解中的最小值是有关的,毕竟后面的「+1」是大家都有的。 ...

