动态规划问题的分类求最大最小值从左上角走到右下角路径的最大数字和最长上升子序列长度计数有多少种方式...有多少种方法选出k个数使得和是sum求存在性取石子游戏，先手是否必胜能不能选出k个数使得和是sum常见动态规划问题的类型坐标型动态规划(20%)：二维数组下标就是坐标，如机器人路线问题序列型动态规划(20%)：划分型动态规划(20%)：给一个字符串或数组让划分成若干段满足一些性质区间型动态规划(15%)：选择连续区间而符合一定条件，f(i,j)背包型动态规划(10%)：一定空间的背包最多带多少物品的问题最长序列型动态规划(5%)：最长上升子序列等类似问题博弈型动态规划(5%)：博弈算出一个人
贪心算法的思想即对于目标T，对于达成它的每一局部都选择最优选项，直到满足或最终近似满足为止，最终结果或许不是全局最优解，但应该是近似最优解，因为它足够简单。每一步都采取局部最优做法！贪婪算法大多时候都是近似最优算法！贪心算法的三步走：第一步：明确到底什么是最优解？第二步：明确什么是子问题的最优解？第三步：分别求出子问题的最优解再堆叠出全局最优解？贪心算法的前提：原问题复杂度过高；求全局最优解的数学模型难以建立；求全局最优解的计算量过大；没有太大必要一定要求出全局最优解，“比较优”就可以。以上情况几乎99.99999999999%就要使用贪心算法的思想来解决问题！分解子问题的方法：1.按串行任务
回溯法回溯法也叫试探法，试探的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。使用回溯法解题的基本步骤如下所示：(1)针对所给问题，定义问题的解空间。(2)确定易于搜索的解空间结构。(3)以深度优
分治法分治算法采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。我们只要求出子问题的解，就可得到原问题的解。在编程过程中，我们经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，我们可以采用“各个击破”的方法。具体做法是先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解法。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的小子问题，依此类推，直至可以直接求出解为止。这就是分治策略的基本思想。使用分治算法解题的一般步骤如下所示：(1)
迭代法迭代法也被称为辗转法，是一种不断用变量的旧值递推新值的过程，在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似。在使用迭代算法解决问题时，需要做好如下3个方面的工作：(1)确定迭代变量在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。(2)建立迭代关系式迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。(3)对迭代
递归法在计算机编程应用中，我们常常遇到代码的递归调用，事实上，递归是一种编程技巧，它是分治思想的一种重要体现。递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。从直观上讲，递归是将大问题化为相同结构的小问题，从待求解的问题出发，一直分解到已经已知答案的最小问题为止，然后再逐级返回，从而得到大问题的解。从本质上讲，计算机在执行递归调用时是一个不断压栈出栈的过程，递归的每一次“递”都是入栈，将函数状态或临时变量的指针入栈，而每一次“归”时都是出栈，将子问题的解逐渐交还给上层调用者。递归算法有如下3个特点:(1)递归过程一般通过函数或子过程来实现。(2)递归算法在函数或子
递推法递推算法犹如稳重的有经验的老将，使用“稳扎稳打”的策略，不断利用已有的信息推导出新的东西。在日常应用中有如下两种递推算法：(1)顺推法：从已知条件出发，逐步推算出要解决问题的方法。(2)逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。顺推法例如斐波那契数列就可以通过顺推法不断递推算出新的数据：兔子问题：有一对兔子,从出生后第3个月起每个月生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子不死,问第二十个月的兔子对数是多少?算法分析：分析:我们要想办法找规律兔子对数：第一个月：1；第二个月:1；第三个月:2；第四个月:3；第五个月:5；第六个月:
一、枚举法枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。使用枚举算法解题的基本思路如下所示：(1)确定枚举对象、枚举范围和判定条件。(2)逐一枚举可能的解，验证每个解是否是问题的解。枚举算法一般按照如下3个步骤进行：(1)题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。(2)判断是否是真正解的方法。(3)使可能解的范围降至最小，以便提高解决问题的效率。什么时候选择枚举法？在任何情况下，都需要选准最合适的对象，无论是枚举还是其他算法思想，这是最关键的。选准(枚举)对象的根本原因在于优化，具体表现为减少求解步骤，缩小求解的解空间