动态规划（C语言实现）

动态规划

动态规划的介绍

动态规划的定义

点这里直接跳转 - - >动态规划
简单点来说，动态规划 = 分治递归 （递推）+ 记忆存储。

什么叫做分治递归（递推）？

分治递归其实既包含了递归这种编程技巧和思维方式，又包含分而治之这种算法思想，简单点来说，递归对于一个递推式而言就是一个式子从后往前算，最前面的项是第一项（已知），我调用很多次函数，就可以拿到这个第一项，然后返回这个第一项就可以求出来其它项的值，具体的内容我们后面博客会详细的提到这个递归。

递归

1.定义

递归：（英语：Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

2.引入

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

以下是一些有助于理解递归的例子：
1.如何给一堆数字排序？答：分成两半，先排左半边再排右半边，最后合并就行了，至于怎么排左边和右边，请重新阅读这句话。
2.你今年几岁？答：去年的岁数加一岁，1999 年我出生。

分而治之

1.定义

定义
分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

2.过程

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

1.分解原问题为结构相同的子问题。
2.分解到某个容易求解的边界之后，进行递归求解。
3.将子问题的解合并成原问题的解。
分治法能解决的问题一般有如下特征：

1.该问题的规模缩小到一定的程度就可以容易地解决。
2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
3.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

什么叫做记忆储存？

即在程序中，将某个重复出现的对象储存起来，下次用到它时，可以直接使用

斐波拉契数列的递归求法

点这里直接跳转 - - >题目—牛客网

斐波拉契数的定义

点这里直接跳转 - - >百度百科

传统的递归解法

递归的关键在于自上而下，利用公式F(n) = F(n-1)+F(n-2)，n>=2。假设我们要算第5个数的斐波拉契数为多少，那么我们只需要知道第4个数和第3个数的结果就可以了，即F(5)= F(4)+F(3)，按照同样的思路去算F(4)与F(3)，在把值返回过来计算即可，这里我们借助图片更好的去理解。

代码实现如下，这里我们只给出了函数部分。

int Fib(int n)
{
  if(n <= 1)
    return n;
    else return Fib(n-1) + Fib(n-2);
}
1
2
3
4
5
6

这种算法虽然在时间复杂度上不占优势，但分而治之的思想很值得借鉴。另外，本人才疏学浅，如有不足，请各位大佬不吝赐教,谢谢！！

动态规划解法

#include <stdio.h>
#include<stdlib.h>
#include <string.h>
#include<assert.h>
int Fib(int n,int* p)
{
 
  p[0] = 0;
  p[1] = 1;
  if(p[n] < 0)
   p[n] = Fib(n-1,p) + Fib(n-2,p);
   return p[n]; 
}
int main() {
	
    int n = 0;
    scanf("%d",&n);
	int* p = (int*)malloc((n+1) * sizeof(int));//注意这里要开辟n+1个数组的大小，因为p[0]也要算上，否则会造成数组越界。
	assert(p);//确保p已经申请空间成功，防止出现空指针的情况
    memset(p,-1,(n+1) * sizeof(int*));//初始化动态数组的所有值为-1，方便知道F(n)是否已经算出
    printf("%d\n", Fib(n,p)); 
    return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

感悟与思考

• 递归来求其实并不是斐波拉契问题的最优解，递推求解更为方便，递归的思路适用于更多的情景，有些场景里面递归有着无法替代的地位，而且动态规划在找工作和面试时也是一个比较重要的板块，相信大家都已经掌握的不错了，没掌握的很好也没关系，可以去做做牛客网的在线编程题点这里直接跳转 - - >牛客网动态规划专题，另外大家对这篇博客有什么改进的地方，欢迎评论区留言，我将一一回复，谢谢大家！！