1、爬楼梯

       题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
       思路分析: 定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
即 dp[i] = d[i-1] + dp[i-2]。
上述问题是一个典型的Fibonacci问题，因此可以使用递归实现。

1
2
3
4
5
6

function test($n = 10) {
   if ($n <= 2) {
       return $n;
   }
  return test($n-1)+ test($n-2);
}

但是 分析发现，使用递归方法，改算法的空间复杂度为O(n),考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。
实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13

function test($n = 10) {
     if ($n <= 2) {
       return $n;
   }
   $pre1 = 1;
   $pre2 = 2;
   for($i = 2; $i< $n ;$i++) {
         $now = $pre1 + $pre2;
        $pre1 = $pre2;
        $pre2 = $now;
   }
   return $now;
}

2、强盗抢劫

         题目描述: 强盗抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。
         思路分析: 定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以
d[i] = max(d[i-1],d[i-2]+num[i]);
实现如下：

1
2
3
4
5
6
7
8
9
10

function test($nums){
    $pre1 = 0;
    $pre2 = 0;
    for($i = 0; $i < count($nums); $i++) {
        $now = max($pre2 + $nums[$i],$pre1);
        $pre2 = $pre1;
        $pre1 = $now;
    }
    return $now;
}

3、强盗在环形街区抢劫

         题目描述: 强盗在一个环形街区进行抢劫，但是不能抢邻近的住户，求最大抢劫量。

         思路分析: 由于是环形房屋，那么意味着第一间房屋和最后一间房屋是紧挨的。我们可以将环形数组拆成从0到numsSize-2,和1到numsSzie-1两部分，然后分别计算两部分的最大抢劫数，最后取两者中的较大值作为结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

$num = array(1,2,3,4,5,6,7,8,9,10);

function rob($num ,$first,$last){
    $pre1 = 0;
    $pre2 = 0;
    for ($i = $first;$i<=$last;$i++) {
        $now = max($pre2+$num[$i],$pre1);
        $pre2 = $pre1;
        $pre1 = $now;
    }
    return $now;
}

function test($num) {
    if(empty($num)) {
        return 0;
    }
    if (1 == count($num)) {
        return nums[0];
    }
    return max(rob($num,0,count($num)-2),rob($num,1,count($num)-1));
}

4、母牛成产

         题目描述: 假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。
         思路分析: 第 N-3 年的所有牛，到第 N 年肯定都是成熟的牛，期间出生的牛肯定都没有成熟。所以
第 i 年成熟的牛的数量为：
dp[i] = dp[i-3]+ dp[i-1];
实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

function test($N = 10) {
    if($N < 0 ) {
        return 0;
    }
    if($N ==1 || $N==2 || $N==3) {
        return $N;
    }
    $pre1 = 1 ;
    $pre2 = 2;
    $pre3 = 3;
    
    for($i = 4; $i<= $N ; $i++) {
        $now = $pre1 + $pre3;
        $pre1 = $pre2;
        $pre2 = $pre3;
        $pre3 = $now;
    }
    return $now;
}

信件错排

         题目描述: 有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量。
         问题说明: 有n个正整数1，2，3，……n，将这n个正整数重新排列，使其中的每一个数都不在原来的位置上，这种排列称为正整数1，2，3，……n的错排
         思路分析: 由题意a1=0，a2=1，当n≥3时，在错排中n必不在第n位，设n放在第k位上（1≤k≤n-1），则第n位上有两种可能：

• 如果第n位上不是k，那么把第n位看作第k位，将n以外的n－1个数进行错排，错排个数是an-1；

• 如果第n位上是k，那么除n和k以外的n－2个数的错排是an-2，
  所以n在第k位上的错排数共有an-1＋an-2，由于k可取1、2、3、4、……、n－1共n－1种取法，所以n个数的错排个数: An= (n-1)(A(n-1) + A(n-2));
  实现如下：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  function error_combination($N = 3) { if ($N <= 1) { return 0; } if($N == 2) { return 1; } $pre1 = 0; $pre2 = 1; for ($i = 3;$i<= $N ;$i++) { $now = ($i-1)*($pre1 +$pre2); $pre1 = $pre2; $pre2 = $now; } return $now; }

  最后

         Fibonacci 数列问题，关键在于找出递推公式，并且都可以使用递归放实现，但递归的空间复杂度都是O（n）,在实现的时候都可以优化成O(1).