C语言刷题之动态规划进阶(一)_c语言动态规划数据结构

目录

1.前言

2.过河卒

        1.题目

         2.初步分析

        3.代码实现

3.打家劫舍

        1.题目

        2.初步分析

        3.代码实现

4.最长上升子序列

        1.题目

        2.初步分析

        3.代码实现

---

1.前言

        前几期我们结束了动态规划的入门训练，相信对动态规划算法的使用和套路有了一定的了解。接下来我们将步入动态规划进阶训练，从一维dp数组逐步过渡到多维dp数组。老样子，本期依旧带来三道题目。上期传送门：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点坐标和马的坐标

输出描述：

输出路径总数

---

          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语言刷题之动态规划入门(三)

我的思路是：建立一个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