社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
《安琪拉与面试官二三事》系列文章
一个HashMap能跟面试官扯上半个小时
一个synchronized跟面试官扯了半个小时《安琪拉教鲁班学算法》系列文章
动态规则是算法中非常重要的一类方法，书本上很多都是列出一堆公式，如果是初学者需要花费很多心血练习之后，才会有那么一刻有顿悟的感觉！本文希望通过使用王者峡谷二位脆皮英雄对话的方式讲解动态规划，让大家在轻松愉快的氛围中搞懂动态规划。
后续会持续更新算法：重点讲 排序、递归、回溯、贪心、深度/广度优先搜索等，顺序不定，希望尽早了解的可以给我留言。
鲁班：安琪拉，你听过动态规划吗？
安琪拉：当然听说过，王者峡谷有个传闻，谁掌握了动态规划，就相当于拿到了屠龙刀，可以biubiubiu 三下砍死大龙。
鲁班：安琪拉妹妹，你能给我讲讲什么是动态规划吗？
安琪拉：鲁班哥哥，看你求知欲这么强，咱俩又都是脆皮的份上，我给你讲讲动态规划。
鲁班：已经搬好小板凳。
安琪拉：动态规划是一种求问题最优解的方法。通用的思路：将问题的解转化成==> 求解子问题，> 递推，>最小子问题为可直接获得的初始状态。
鲁班：你这么说完我还是很蒙啊！ 能不能不打嘴炮，给我演示一下这个技能呗！
安琪拉：可以啊！我们找个小怪演示一下，请看第一题（斐波拉契数列）：
这个数列特点是从第三项开始，每一项都是前二项的和：2 = 1 + 1，3 = 1 + 2；
鲁班：这个我知道怎么做，你看我的，手写代码在此：
public class FibonacciSequence {
//求斐波拉契第n项
public int fibonacci(int n){
if(n == 1 || n == 2){
return 1;
}else{
return fibonacci(n-1) + fibonacci(n-2);
}
}
}
安琪拉：你这个解法其实就有动态规划的思想，但是还可以做些优化！因为中间有大量的重复计算。
比如，我们求数列中第100个数是多少？ 递归会如下所示：
安琪拉： 如
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
