#1037 : 数字三角形时间限制:10000ms单点时限:1000ms内存限制:256MB问题描述小Hi和小Ho在经历了螃蟹先生的任务之后被奖励了一次出国旅游的机会，于是他们来到了大洋彼岸的美国。美国人民的生活非常有意思，经常会有形形色色、奇奇怪怪的活动举办，这不，小Hi和小Ho刚刚下飞机，就赶上了当地的迷宫节活动。迷宫节里展览出来的迷宫都特别的有意思，但是小Ho却相中了一个其实并不怎么像迷宫的迷宫——因为这个迷宫的奖励非常丰富~于是...
一、斐波那契数列（递归VS动态规划）1、斐波那契数列——递归实现（python语言）——自顶向下递归调用是非常耗费内存的，程序虽然简洁可是算法复杂度为O(2^n)，当n很大时，程序运行很慢，甚至内存爆满。1def fib(n): 2#终止条件，也就是递归出口3if n == 0 or n == 1: 4return 1 5else: 6#递归条件7return (fib(n-1) + fib(n - 2))2、斐波那契数列——动态规划实现（python语言）——自底向上动态规划——将需要重复计算的问题保存...
名词解释：DFS(Dynamic Plan)：动态规划DFS(Depth First Search)：深度优先搜索DFS与DP的关系很多情况下，dfs和dp两种解题方法的思路都是很相似的，这两种算法在一定程度上是可以互相转化的。想到dfs也就常常会想到dp，当然在一些特定的适用场合下除外。dp主要运用了预处理的思想，而dfs则是类似于白手起家，一步步探索。一般来讲，能够预处理要好些，好比战争前做好准备。dfs和dp都是十分重要的基础算法，在各个竞赛中都有涉及，务...
DP算法总结&专题训练2（树形DP） 1. 前言2. 练习题[P2585 [ZJOI2006]三色二叉树](https://www.luogu.com.cn/problem/P2585)[P4516 [JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516)[P2607 [ZJOI2008]骑士](https://www.luogu.com.cn/problem/P2607)1. 前言 本篇博文是树形 DP 的练习题。 没有学过树形 DP？ 传送门：算法学习笔记：树形 DP 树形 DP 的题目一般是比较容易看出来的 （树难道还看不出来吗），其唯一难点在...
道格拉斯-普克算法(Douglas–Peucker algorithm，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法)是将曲线近似表示为一系列点，并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯拉默（Urs Ramer）于1972年以及大卫道格拉斯（David Douglas）和托马斯普克（Thomas Peucker）于1973年提出，并在之后的数十年中由其他学者予以完善。 算法的基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离...
目录 声明 dfs与dp的关系 经典例题-数字三角形 - POJ 1163 题目 dfs思路 解题思路 具体代码dp思路 解题思路 具体代码声明 本文不介绍dfs、dp算法的基础思路，有想了解的可以自己找资源学习。 本文适合于刚刚接触dfs和dp算法的人，发现两种算法间的内在联系。 本人算法之路走之甚短，如果理解出现问题欢迎大家的指正，我会分享基于我目前理解到的算法思想。 dfs与dp的关系 很多情况下，dfs和dp两种解题方法的思路都是很相似的，这两...
表情包形象取自番剧《猫咪日常》那我也整一个 曾几何时，笔者是个对算法这个概念漠不关心的人，由衷地感觉它就是一种和奥数一样华而不实的存在，即便不使用任何算法的思想我一样能写出能跑的程序 直到一年前帮同学做了个手机游戏demo才发现了一个严峻的问题**为啥*一样的画面能跑出ppt的质感？**虽然发现当时的问题主要出现在使用了一个有bug的API，它导致了低性能的循环调用，但是从那时便开始就重新审视算法了，仅仅一个函数就能...
一、斐波那契数列（递归VS动态规划）1、斐波那契数列——递归实现（python语言）——自顶向下 递归调用是非常耗费内存的，程序虽然简洁可是算法复杂度为O(2^n)，当n很大时，程序运行很慢，甚至内存爆满。1 def fib(n): 2 #终止条件，也就是递归出口 3 if n == 0 or n == 1: 4 return 1 5 else: 6 #递归条件 7 return (fib(n-1) + fib(n - 2))2、斐波那契数列——动态规划实现（python语言）—...