算法汇总学习记录
2021-01-24 00:17
标签：先后 pre 台阶 boa 动态规划 一个 递归 思路分析 需要 1.斐波那契数列 (推荐使用动态规划的，当输入n=40的时候就能明显的感觉出递归的不足了) 对于：下面的题，得出结论，见题需要按照逻辑去分析，不要莽写，下面的题我莽写想了那么多，写了一百行的代码最后发现还少考虑了每个划分后不同划分之间可能重复的情况，如果能够按照下面的思路分析，可能感觉好像不是特别的直观，但是代码按照这样逻辑去写就是可以实现出来的哦。 =============↓题干↓============= 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 =============↓分析↓============= //对于本题, 前提只有 一次 1阶或者2阶的跳法。 //a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1); // b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2) //c.由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) //d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2 //e.可以发现最终得出的是一个斐波那契数列： 以上分析后，解题思路竟然是斐波那契数列，对于斐波那契数列我们使用动态规划来做是最香的！ ============================== 算法汇总学习记录 标签：先后 pre 台阶 boa 动态规划 一个 递归 思路分析 需要 原文地址：https://www.cnblogs.com/ningxinjie/p/12869023.html这个递归思想是最简单的了
static int feiboArr(int n)
{
if (n == 0) { return 0; }
else if (n==1) { return 1; }
else if (n==2) { return 1; }
else
{
return feiboArr(n-1) + feiboArr(n-2);
}
} //使用动态规划来做，这个方法我觉得更好，因为比递归占用空间更小了。
//这个思路非常简单，就是一个个记录前一个是啥就好了，f记录本次的那一个，g记录本次的下一个
public static int JumpFloor2(int n)
{
int f = 0, g = 1;
while (n-- > -1)
{
g += f;
f = g - f;//上面g=g+f这里f其实就是加之前的那个g，也就是本次的那一个
}
return f;
}