动态规划和 (或) 递归的应用举例 (C语言实现)

╰+哭是因爲堅強的太久メ 2023-03-01 05:43 76阅读 0赞

上一节中，我们对动态规划和 (或) 递归进行了介绍。这一节，我们进行应用举例。

## 1、Fabnacci函数 ##

Fabnacci函数的表达式：f(n) = f(n - 1) + f(n - 2)。其中，当n = 1时，f(1) = 1；当n = 2时，f(2) = 2。根据这个表达式，显然可以用递归和动态规划写出代码。  
递归代码如下：

int Fabnacci_Recurrence(int n)
    {
        
    	if(n == 1 || n == 2)
    	{
        
    		return n; //递归的出口 
    	}
    	return Fabnacci_Recurrence(n - 1) + Fabnacci_Recurrence(n - 2); //递归
    }

动态规划代码如下：

int Fabnacci_Dynamic(int n)
    {
        
    	int arr[100]; //将计算得到的中间结果存放在arr中 
    	arr[1] = 1; //f(1) = 1
    	arr[2] = 2; //f(2) = 2
    	
    	//从arr中获取中间结果，计算f(n)。并将计算结果存放在arr中 
    	for(int i = 3; i <= n; i++)
    	{
        
    		arr[i] = arr[i - 1] + arr[i - 2];
    	}
    	return arr[n]; //arr[n]中存放了第n个计算结果。
    }

递归方式代码看上去更简洁，动态规划方式相对比较复杂。两种方式的效率差别很大：  
递归方式: 时间复杂度为O(N!)，计算f(45)需要15秒左右。  
动态规划: 时间复杂度为O(N)，可以瞬间算出f(45)的结果。

## 2、走迷宫 ##

有5 \* 5的表格，黄色的格子是起点，绿色的是终点。每次只能往右或往下走一格。请问一共有多少种走法？

![在这里插入图片描述][2020072212370292.png]  
数学分析：最多往右走4格，往下走4格。所以一共是 = 70种走法。写代码之前的分析：最右边的时候只能往下走，所以最右边的时候只有一种走法。同样，最下面的时候只能往右走，也只有一种走法。

![在这里插入图片描述][20200722123717691.png]  
假设目标位置的坐标是(1,1)，当前坐标为(x, y)。在该坐标时，一共只有两种走法：  
f(x, y) = f(x - 1, y) + f(x, y - 1)。

利用递归方式编写代码：时间复杂度 O(N!)。

int maze_Recurrence(int x, int y)
    {
        
    	if(x == 1 || y == 1)
    	{
        
    		return 1; //递归的出口
    	}
    	else
    	{
        
    		return maze_Recurrence(x - 1, y) + maze_Recurrence(x, y - 1); //递归
    	}
    }

利用动态规划法编写代码：时间复杂度 O(N ^ 2)。

int maze_Dynamic(int x, int y)
    {
        
    	int arr[10][10];
    
    	//初始化：已经贴边时就只有一种方案
    	for (int i = 1; i <= x; i++)
    	{
        
    	    arr[i][1] = 1;
    	}
    	for (int i = 1; i <= y; i++)
    	{
        
    	    arr[1][i] = 1;
    	}
    
    	//从2开始循环计算，
    	//从arr中获取之前的计算结果，并将当前的计算结果也存放到arr中 
    	for (int i = 2; i <= x; i++)
    	{
        
    	    for (int j = 2; j <= y; j++)
    	    {
        
    	        arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
    	    }
    	}
    
    	//显示二维数组 (所有的计算结果)
    	for (int i = 1; i <= x; i++)
    	{
        
    	    for (int j = 1; j <= y; j++)
    	    {
        
    	        printf("%d, ",arr[i][j]);
    	    }
    	    printf("\r\n");
    	}
    	return arr[x][y]; //返回结果 
    }

打印结果方阵如下：

![在这里插入图片描述][20200722123738800.png]

## 3、求一个数组中，连续的几个数的和的最大值。 ##

int arr \[\] = \{-3, 1, 4, -2, 3, 4, -2, 4, -3\}。 答案是12。  
一共三种方案：暴力求解、递归 (分治法)、动态规划。

暴力求解：  
在数组arr中求连续的几个数：起点有n种可能，终点有n种可能。  
求连续的几个数和的时间复杂度为O(N)。综合起来，这种方式的时间复杂度为O(N^3)。实现代码如下：

int fun1() 
    {
        
    	int sum = 0; //记录累加的和
    	int max = -999; //假设-999是最小值
    	for(int i = 0; i < size; i++) //遍历所有的起点 
    	{
        
    		//遍历所有的终点。要求起点的index <= 终点的index
    		//所以j的起始值是i，而不是0。这样可以节约一半时间
    		for(int j = i; j < size; j++)  
    		{
        
    			sum = 0; // 每次都要初始化sum 
    			for(int k = i; k < j; k++) //数组求和：计算第i ~ j个元素的和
    			{
        
    				sum += arr[k]; //用sum记录数组的和
    			}
    			if (max < sum)
    			{
        
    				max = sum; //用sum不断更新max
    			}
    		}
    	}
    	return max;
    }

递归求解  
一共有三种情况：  
1、要的数组在左边半个arr中  
2、要的数组在右边半个arr中  
3、要的数组跨越了两个arr。这时从左边半个arr往index减小的方向统计，右边半个arr往index增大的方向统计。向两个方向统计的过程就是动态规划的过程，省略本代码，参看动态规划部分即可。  
递归求解的时间复杂度为O(N \* logN)。

动态规划：  
以 arr\[i\]作为终点的一段连续数据  
所有结果都保存在数组 results中，且 results\[0\] = arr\[0\]  
下面分情况进行讨论：  
如果 results\[i - 1\] < 0 < arr\[i\]，则results\[i\] = arr\[i\]。  
如果 results\[i - 1\] > 0，arr\[i\] > 0，则results\[i\] = results\[i - 1\] + arr\[i\]。  
如果 results\[i - 1\] < 0，arr\[i\] < 0。当results\[i - 1\] < arr\[i\] < 0时，results\[i\] = arr\[i\]。  
如果 results\[i - 1\] < 0，arr\[i\] < 0。当results\[i\] < arr\[i - 1\] < 0时，results\[i\] = arr\[i - 1\]。  
如果 results\[i - 1\] > 0 > arr\[i\]，则results\[i\] = arr\[i - 1\]。  
综合上述情况，results\[i\]的表达式只有3种：  
1、results\[i\] = arr\[i\]  
2、results\[i\] = results\[i - 1\] + arr\[i\]  
3、results\[i\] = arr\[i - 1\] (不符合：arr\[i\]作为终点的一段连续数据)，舍去这种情况，也就是说符合要求的只有两种可能，只要求这两种可能的最大值即可。即：  
results\[i\] = max(arr\[i\], results\[i - 1\] + arr\[i\])  
这种方式的时间复杂度为O(N)。

int fun3()
    {
        
    	int results [size]; //用results数组记录所有的中间结果 
    	int max = arr[0]; //初始状态下，arr[0]就是最大值 
    	results[0] = arr[0]; //arr[0]就是最大值，存入result[0]中 
    	
    	//动态规划计算 
    	for(int i = 1; i < size; i++)
    	{
        
    		//获得 arr[i]与results[i - 1] + arr[i]中的较大值，并记录在results[i]中 
    		results[i] = max(arr[i], results[i - 1] + arr[i]);
    	}
    	
    	//更新max。可以把动态规划和更新max合并在一起 
    	for(int i = 0; i < size; i++)
    	{
        
    		if(max < results[i])
    		{
        
    			max = results[i];
    		}
    	}
    	return max;
    }

动态规划和更新max合并在一起，可以缩短代码的长度：

int fun4()
    {
        
    	int results [size]; //用results数组记录所有的中间结果 
    	int max = arr[0]; //初始状态下，arr[0]就是最大值 
    	results[0] = arr[0]; //arr[0]就是最大值，存入result[0]中 
    	
    	//动态规划计算 
    	for(int i = 1; i < size; i++)
    	{
        
    		//获得 arr[i]与results[i - 1] + arr[i]中的较大值，并记录在results[i]中 
    		results[i] = max(arr[i], results[i - 1] + arr[i]);
    
    	if (max < results[i]) //更新max。
    		{
        
    			max = results[i];
    		}
    	}
    	return max;
    }

## 4、统计字符数组中连续相同的字符数 ##

在字符数组char letterArr \[\] = \{‘a’, ‘a’, ‘a’, ‘b’, ‘b’, ‘c’, ‘d’, ‘d’, ‘d’, ‘d’, ‘a’, ‘a’\}中，统计连续相同的字符数并输出。这个字符数组中的内容不一定是有序的。输出结果为：a3b2c1d4a2。

这里只使用动态规划的方式求解：  
使用数组numArr\[20\]记录动态规划中的中间结果。  
如果letterArr\[i - 1\]和letterArr\[i\]相同，则 numArr\[i\] = numArr\[i - 1\] + 1；  
如果letterArr\[i - 1\]和letterArr\[i\]不同，则重新从1开始累加。

//统计字符数组中连续相同的字符数 
    #include<stdio.h>
    #include<stdlib.h>
    
    int size = 0; //数组长度
    int main()
    {
        
    	char letterArr [] = {
        'a', 'a', 'a', 'b', 'b', 'c', 'd', 'd', 'd', 'd', 'a', 'a'};
    	size = sizeof(letterArr) / sizeof(char); //数组长度
    	 
    	int numArr[20]; //动态规划，将结果存放在数组numArr中
    	numArr[0] = 1; //numArr的首元素为1
    	
    	for(int i = 1; i < size; i++) //从1开始遍历 
    	{
        
    		//如果letterArr[i - 1]和letterArr[i]相同，则 numArr[i] = numArr[i - 1] + 1
    		if(letterArr[i] == letterArr[i - 1])
    		{
        
    			numArr[i] = numArr[i - 1] + 1; 
    		}
    		else //如果letterArr[i - 1]和letterArr[i]不同，则重新从1开始累加
    		{
        
    			//可以输出之前的数据。也可以将数据另外处理 
    			//这里不能输出最后一个数据
    			printf("%c%d", letterArr[i - 1], numArr[i - 1]); 
    			numArr[i] = 1;
    		}
    	}
    	printf("%c%d", letterArr[size - 1], numArr[size - 1]); //输出最后一个数据
    	return 0;
    }

[2020072212370292.png]: /images/20230209/1cda774495e74986a33b9687edcae474.png
[20200722123717691.png]: /images/20230209/a4f6264ab2b74c7fac6263a9905e29cf.png
[20200722123738800.png]: /images/20230209/49455964ddc2424a8b0c51c2375078b8.png