C语言刷题之动态规划进阶(一)

ゝ一纸荒年。 2024-03-30 10:07 101阅读 0赞

**目录**

1.前言

2.过河卒

1.题目

2.初步分析

3.代码实现

3.打家劫舍

1.题目

2.初步分析

3.代码实现

4.最长上升子序列

1.题目

2.初步分析

3.代码实现

--------------------

### 1.前言 ###

前几期我们结束了动态规划的入门训练，相信对动态规划算法的使用和套路有了一定的了解。接下来我们将步入动态规划进阶训练，从一维dp数组逐步过渡到多维dp数组。老样子，本期依旧带来三道题目。上期传送门：[C语言刷题之动态规划入门(三)][C]。

> 这三道题目分别是：过河卒，打家劫舍和最长上升子序列

### 2.过河卒 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 棋盘上 A点有一个过河卒，需要走到目标 B点。卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
> 
> 棋盘用坐标表示，A 点 (0, 0)、B点(n,m)，同样马的位置坐标是需要给出的。
> 
> 现在要求你计算出卒从 A点能够到达 B点的路径的条数，假设马的位置(x,y)是固定不动的，并不是卒走一步马走一步。
> 
> 注：马一次跳跃到达的点(x1,y1)和马原坐标(x,y)的关系是 |x1-x|+|y1-y|=3 ，且∣x1−x∣+∣y1−y∣=3，且x1!=x,y1!=y
> 
> 数据范围：1≤n,m≤20 ，马的坐标0≤x,y≤20 ,1≤a,b,c,d≤1000
> 
> #### 输入描述： ####
> 
> 仅一行，输入 n,m,x,y 四个正整数。分别表示B点坐标和马的坐标
> 
> #### 输出描述： ####
> 
> 输出路径总数

![4119251f55f24de797b54233807fa481.png][]

--------------------

#### 2.初步分析 ####

题目要求求出A到B点卒的路径总数，由于是一个二维平面，于是我们的dp数组就是一个(n+1)\*(m+1)的二维数组，数组每个元素代表到达当前点的路径总数。然后通过分析题目，初始化dp数组，找出状态转移方程，即可求解本题。

> **我的思路是**：创建一个(n+1)\*(m+1)的dp数组，由题目可得卒只能往下走和往右走，且不能走到马的控制点。因此，我们可以建立一个函数判断某一点是否是马的控制点，如果是，则将此点的路径置0，代表不能到达此点;如果不是，则通过dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i\]\[j-1\]对dp数组进行赋值。主要代码如下：

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    #include<stdlib.h>
    int Judge(int i, int j, int x, int y)      //判断是否为马的控制点
    {
    	if ((abs(i - x) + abs(j - y) == 3 && i != x && j != y) || (i == x && j == y))
    	{
    		return 1;
    	}
    	else
    		return 0;
    }
    int main()
    {
    	int n = 0, m = 0, x = 0, y = 0;       //代表b点坐标和马的坐标
    	scanf("%d %d %d %d", &n, &m, &x, &y);
    	int** dp = (int**)malloc(sizeof(int*) * (n+1));     //建立dp数组(二维)
    	for (int i = 0; i < n+1 ; i++) 
    	{
    		dp[i] = (int*)malloc(sizeof(int) * (m+1));
    	}
    	dp[0][0] = 1;                         //初始化数组
    	for (int i = 1; i < n + 1; i++)       //初始化第一行第一列，只能往上或往下其中之一
    	{
    		if (Judge(i,0,x,y)==0)            //不是控制点
    		{
    			dp[i][0] = dp[i-1][0];
    		}
    		else                              //是控制点
    		{
    			dp[i][0] = 0;
    		}
    	}
    	for (int j = 1; j < m + 1; j++)        
    	{
    		if (Judge(0, j, x, y) == 0)         
    		{
    			dp[0][j] = dp[0][j-1];         
    		}
    		else
    		{
    			dp[0][j] = 0;
    		}
    	}
    	for (int i = 1; i < n + 1; i++)          //遍历dp数组
    	{
    		for (int j = 1; j < m + 1; j++) 
    		{
    			if (Judge(i, j, x, y) == 0)
    			{
    				dp[i][j] = dp[i][j - 1]+dp[i-1][j];
    			}
    			else
    			{
    				dp[i][j] = 0;
    			}
    		}
    	}
    	printf("%d", dp[n][m]);
        free(dp);
    	return 0;
    }

> **注:当n和m超过20时，dp数组的数据类型需用long long，否则数据过大会超出**

### 3.打家劫舍 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
> 
> 给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
> 
> 数据范围：数组长度满足1≤n≤2×100000 ，数组中每个值满足1≤nums\[i\]≤5000
> 
> #### 输入描述： ####
> 
> 第一行输入一个正整数 n ，表示数组的长度。
> 
> 第二行输入 n 个正整数，表示每个房间存有的现金。
> 
> #### 输出描述： ####
> 
> 输出最多的偷窃金额

--------------------

#### 2.初步分析 ####

由于首尾相连且题目要求所偷的房间不能相连，则首尾不能都偷。于是可以分成两种情况，分别为包含首项和不包含首项，如果包含首项，则最大值就为dp\[n-2\]或dp\[n-3\]，如果包含首项，则最大值为dp\[n-1\]或dp\[n-2\]，然后再求出两种情况最大值即可求出最多偷窃金额。

> **我的思路是：**根据上述分析，建立两个dp数组，分别代表包含首项的数组和不包含首项的数组，然后依次初始化求最大值。其中，两个dp数组的状态转移方程都是：
> 
> dp\[i\]=dp\[arr\]+max(dp\[i-2\],dp\[i-3\]);
> 
> 由于我们i是从3开始，因此，我们在进行遍历数组之前，需要根据dp数组种类对前三项进行初始化。最后输出两个dp数组的较大值即可。

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    #include<stdlib.h>
    int max(int x, int y)
    {
    	return x > y ? x : y;
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int *arr=(int*)malloc(sizeof(int) * n);
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    	if (n == 1)                               //只有一个数，则输出
    	{
    		printf("%d",arr[0]);
    	}
    	if (n == 2)                             //只有两个数，输出较大一个
    	{
    		printf("%d", max(arr[0], arr[1]));
    	}
    	int* dp1 = (int*)malloc(sizeof(int) * n);       //包括首项的
    	int* dp2 = (int*)malloc(sizeof(int) * n);        //不包括首项
    	dp1[0] = arr[0];                                 //赋初值
    	dp1[1] = arr[1];
    	dp1[2] = dp1[0] + arr[2];
    	for (int i = 3; i < n; i++)
    	{
    		dp1[i] = max(arr[i]+dp1[i-3], arr[i] + dp1[i - 2]);  
    	}
    	int max1 = max(dp1[n - 2], dp1[n - 3]);  //包括首项，则尾项不包括，此时最大值为前两项之一
    	dp1[0] = 0;
    	dp1[1] = arr[1];
    	dp1[2] = arr[2];
    	for (int i = 3; i < n; i++)
    	{
    		dp1[i] = max(arr[i] + dp1[i - 3], arr[i] + dp1[i - 2]); 
    	}
    	int max2 = max(dp1[n-1], dp1[n - 2]);//不包括首项，此时最大值为尾项或前一项
    	printf("%d", max(max1, max2));       //取两种情况最大值
        free(dp1);
        free(dp2);
    	return 0;
    }

### 4.最长上升子序列 ###

#### 1.题目 ####

> ### 描述 ###
> 
> 给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。  
> 所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。  
> 例如 \[1,5,3,7,3\] 数组，其子序列有：\[1,3,3\]、\[7\] 等。但 \[1,6\]、\[1,3,5\] 则不是它的子序列。  
> 我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i 和 j 满足 i<j且arr\[i\]>=arr\[j\]
> 
> 数据范围：0≤n≤1000 , |arr\[i\]|≤10^9  
> 要求：时间复杂度 O(n^2),空间复杂度 O(n)
> 
> #### 输入描述： ####
> 
> 第一行输入一个正整数 n ，表示数组的长度  
> 第二行输入 n 个整数表示数组的每个元素
> 
> #### 输出描述： ####
> 
> 输出最长严格上升子序列的长度

--------------------

#### 2.初步分析 ####

本题的总体思路其实和上期总结的求连续最大子数组的思路一样，详情请看：[C语言刷题之动态规划入门(三)][C 1]

> **我的思路是：**建立一个dp数组，数组的每个元素代表包含当前元素的最长严格上升子数组，然后再遍历前i个元素，找出小于当前项的元素，我们可以很轻松地得出状态转移方程：
> 
> dp\[i\]=max(dp\[j\]+1,dp\[i\])
> 
> 然后再遍历dp数组找出最大值即可得出答案。

--------------------

#### 3.代码实现 ####

#include<stdio.h>
    #include<stdlib.h>
    int Max(int x, int y)
    {
    	return x > y ? x : y;
    }
    int main()
    {
    	int n = 0;
    	scanf("%d", &n);
    	int *arr =(int *)malloc(n * sizeof(int));
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d", &arr[i]);
    	}
    	int* dp = (int*)malloc(n * sizeof(int));   //存储包含当前项的最长长度的dp数组
    	for (int i = 0; i < n; i++)                //赋初值，默认为1
    	{
    		dp[i] = 1;
    	}
    	for (int i = 0; i < n; i++)
    	{
    		for (int j = 0; j < i; j++)           //查找前i项是否存在比arr[i]小的元素
    		{
    			if (arr[i] > arr[j])               //找到了
    			{
    				dp[i] = Max(dp[j] + 1,dp[i]);  //dp[i]为其中最长的那个
    			}
    		}
    	}
    	int max = dp[0];
    	for (int i = 1; i < n; i++)
    	{
    		if (dp[i] > max)
    		{
    			max = dp[i];                       //找出dp数组的最大值，即为所求
    		}
    	}
    	printf("%d", max);
    	return 0;
    }

--------------------

***以上，就是动态规划进阶刷题(一)的全部内容。***

***制作不易，能否点个赞再走呢qwq***

[C]: http://t.csdn.cn/YkDfn
[4119251f55f24de797b54233807fa481.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/d69a66cfbfb74c53acdda99d37fba3f1.png
[C 1]: http://t.csdn.cn/HOuHb