IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 算法 || 动态规划I -> 正文阅读

[数据结构与算法]算法 || 动态规划I

递归

函数调用自身的过程成为递归,调用自身函数称为递归函数,用递归方式解决问题的算法称为递归算法。

  • 函数调用自身的实现方式
  1. 直接调用自身
int funciton(/*...*/) {
    //......
    //调用自身
    function(/*...*/);
    //......
}
  1. 间接调用自身
int funciton(/*...*/) {
    //......
    //调用自身
    function(/*...*/);
    //......
}
//function1() 函数内部调用了 function2() 函数,而 function2() 函数内部又调用了 function1() 函数。也就是说,function1() 函数间接调用了自身
  • 递归求n!
long long funMul(long long n)
{
	if (n == 1 || n == 0)return 1;
	return n * funMul(n - 1);
}
int main()
{
	int n ;
	cin >> n;
	cout << funMul(n) << endl;
	return 0;
}

递归底层实现机制

  • 当一个函数直接或间接调用自身时,称这个函数为调用者,将直接或间接调用的自身称为被调用者

  • 递归函数执行时,调用者会将执行代码的权力移交给被调用者,同时还可能会向被调用者传输一些数据。此后,调用者将暂停执行,直至被调用者执行完成并将执行代码的权力交换给调用者后,它才能继续执行。

  • 为了确保调用者能够从暂停状态继续执行,当发生递归调用时,多数编程语言都使用栈结构保存调用者的状态信息,包括暂停时局部变量的值、寄存器中保存的数据等等。
    ·

F(n) 调用了 F(n-1),因此 F(n) 会暂停执行,将执行代码的权力移交给 F(n-1),F(n) 的暂停状态也会入栈保存;同样的道理,F(n-1) 中调用了 F(n-2),所以 F(n-1) 暂停执行,暂停状态入栈保存,执行代码的权力移交给 F(n-2)…直至递归停止,执行代码的权力会移交给栈中最顶部的函数,该函数的暂停状态信息会从栈中取出并恢复,该函数继续执行,执行完成后再将执行权力移交给栈顶的函数。直至 F(n) 出栈并执行完成,整个递归过程才算完成

分治策略

  • 大规模的问题–> 划分成相同的小规模的问题

  • 先将整个问题拆分成多个相互独立且数据量更少的小问题,通过逐一解决这些简单的小问题,最终找到解决整个问题的方案

  • 分治策略解决步骤

  1. 分:将整个问题划分成多个相对独立、涉及数据量更少的小问题,有些小问题还可以划分成很多更小的问题,直至每个问题都不可再分;
  2. 治:逐个解决所有小问题
  3. 合并:将所有小问题的解决方案合并到一起,找到整个问题的方案
    在这里插入图片描述
  • 分治策略的优缺点
  1. 优点: 小问题之间是相互独立的,处理次序不分先后,因此可以采用“并行”的方式让计算机同时处理多个小问题,提高问题的解决效率
  2. 缺点: 需要与递归算法搭配使用,会耗费大量的时间和内存空间

求数组的最大值和最小值

分治算法与二分查找结合

int Get_Max(int* arr, int left, int right)
{
	if (arr == nullptr)return -1;
	if (right - left == 0)return arr[left];  //数组中只有一个元素
	if (right - left <= 1)     //数组中有两个数字
	{
		return arr[left] >= arr[right] ? arr[left] : arr[right];
	}
	int mid = (right - left) / 2 + left;     //找到中间的元素
	int max_leftmid = Get_Max(arr, left, mid); //得到左边最大值
	int max_rightmid = Get_Max(arr, mid + 1, right); //得到右边最大值
	return max_leftmid >= max_rightmid ? max_leftmid : max_rightmid; //比较 得到整个区域的最大值
}
int Get_Min(int* arr, int left, int right) //有错误 输出结果错误
{
	if (arr == nullptr)return -1;
	if (right - left == 0)return arr[left];
	if (right - left <= 1)
	{
		return arr[left] <= arr[right] ? arr[left] : arr[right];
	}
	int mid = (right - left) / 2 + left;
	int min_leftmid = Get_Min(arr, left, mid);
	int min_rightmid = Get_Min(arr, mid + 1, right);
	return min_leftmid <= min_rightmid ? min_leftmid : min_rightmid;
}

int main()
{
	int n[2] = {};
	int len = sizeof(n) / sizeof(n[0]);
	cout << "输入"<<len<<"个数组元素:" ;
	for (int i = 0; i < len; ++i)
	{
		cin >> n[i];
	}

	cout << "最大值为:" << Get_Max(n, 0, len) << endl;
	cout << "最小值为:" << Get_Min(n, 0, len) << endl;
	return 0;
}

动态规划

  • Dynamic Programming (DP)

  • 求一个问题的最优解(最大值或最小值),而且该问题能够分解成若干个子问题,并且子问题之间还有重叠的更小的子问题,则可以考虑动态规划求解问题。

  • 特点

特点例题分析
1. 问题的目标是求一个问题的最优解(最大值或最小值)– 长度为n的绳子剪成若干段,求各段长度乘积最大
2. 整体问题的最优解是依赖各子问题的最优解– 第一刀剪在长度为i的位置,则剪出来的长度分别为i和n-i的两段。我们要想得到整个问题的最优解fn),那么要同样用最优化的方法把长度为i和n-i的两段分别剪成若干段,使得它们各自剪出的每段绳子的长度乘积最大。
3. 把大问题分解成若干个子问题,这些子问题之间有相互重叠的更小的子问题– 假设绳子最初的长度为10,我们可以把绳子剪成长度分别为4和6的两段,也就是f(4)和f(6)都是f(10)的子问题。接下来分别求解这两个子问题。我们可以把长度为4的绳子剪成均为2的两段,即f(2)是f4)的子问题。同样,我们也可以把长度为6的绳子剪成长度分别为2和4的两段,即f(2)和f(4)都是f(6)的子问题。我们注意到f(2)是f(4)和f(6)公共的更小的子问题。
4. 从上往下分析问题,从下往上求解问题– 从解决最小问题开始,把以解决的子问题的最优解存储下来(一维或二维数组中),并把子问题的最优解组合起来逐步解决大的问题
  • 五大步骤
  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组
  • 剪绳子问题
/*
剪绳子:长度为n的绳子,剪成m段,每段绳子的长度k[0],k[1],..k[m], (n>1,m>1)
求解k[0]xk[1]xk[2]...可能的最大乘积是多少? f(n)表示长度为n的剪完后的乘积最大值
第一刀 可能的长度为1,2,,,n-1, 递归公式: f(n)=max(f(i)*f(n-i)
绳子长度为2时,剪成两端为1,则f(2)=1;
绳子长度为3时,剪成两端为1,2;或者长度为1,1,1,三段,则f(3)=2;

*/


int MaxCutting(int len)
{
	if (len < 2) return 0;
	if (len == 2)return 1;
	if (len == 3)return 2;

	int* product = new int[len + 1];
	//数组存放最优解 第i个元素表示吧长度i的绳子剪成若干段后长度乘积的最大值 f(i)
	product[0] = 0;
	product[1] = 1;
	product[2] = 2;
	product[3] = 3;

	int max = 0;

	for (int i = 4; i <= len; ++i)    //顺序递增 自下而上
	{
		max = 0;
		for (int j = 1; j <= i / 2; ++j)     //只需要找到i/2处,之后的组合都是前面计算过的
		{
			int pro = product[j] * product[i - j];
			if (max < pro) max = pro;
			product[i] = max;    //每次计算完有比上次更优解的 就保存在product中
		}
	}
	max = product[len];
	delete[]product;
	return max;
}
int main()
{
	cout << "输入绳子长度:  ";
	int n = 0;
	cin >> n;

	cout << MaxCutting(n) << endl;
	return 0;
}


  • 斐波那契数列
/*
斐波那契数列:后一项等于前n-1项加上前n-2项
1,1,2,3,5...
*/

int Fibonacci(int n)
//时间复杂度:O(n)     空间复杂度: O(n)
int fib(int N) {   
	if (N <= 1) return N;
	vector<int> dp(N + 1);
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[N];
}
//时间复杂度:O(n)     空间复杂度: O(1)
int fib_2(int N) {
	if (N <= 1) return N;
	int dp[2];
	dp[0] = 0;
	dp[1] = 1;
	for (int i = 2; i <= N; i++) {
		int sum = dp[0] + dp[1];
		dp[0] = dp[1];
		dp[1] = sum;
	}
	return dp[1];
}
//递归 时间复杂度:O(2^n)  空间复杂度:O(n)
int fib_3(int N) {
	if (N < 2) return N;
	return fib(N - 1) + fib(N - 2);
}
int main()
{
	for (int i = 0; i < 5; i++)
	{
		cout << fib(i) << "  ";
	}
	cout << endl;
	return 0;
}
  • 青蛙跳台阶问题
    1
/*
跳台阶问题:
1.一只青蛙一次可以跳上1级台阶,也可以跳上2级,
找出规律
先跳一层,子问题变为求 f(n-1)个跳法
先跳两层,子问题变为求f(n-2)个跳法
第n层                                                                                                                :f(n)=f(n-1)+f(n-2)
*/
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了,防止空指针
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) { // 注意i是从3开始的
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
	int climbStairs_2(int n) {
		if (n <= 1) return n;
		int dp[3];
		dp[1] = 1;
		dp[2] = 2;
		for (int i = 3; i <= n; i++) {
			int sum = dp[1] + dp[2];
			dp[1] = dp[2];
			dp[2] = sum;
		}
		return dp[2];
	}
int Jump_1(int n) //一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法
{
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n == 2) return 2;
	return Jump_1(n - 1) + Jump_1(n - 2);
}


int Jump_2(int n) //一只青蛙一次可以跳上1级台阶,也可以跳上2级,也可以跳上n阶,求该青蛙跳上一个 n 级的台阶总共有多少种跳法
{
	if (n == 0)return 0;
	if (n == 1) return 1;
	return 2 * Jump_2(n - 1);
}
int main()
{
	int n = 0;
	cin >> n;
	cout << Jump_1(n) << endl;
	return 0;
}
  • 最小花费爬梯子
/*
数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。
每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。

*/

int minCostClimbingStairs(vector<int>& cost) {
	vector<int> dp(cost.size());
	dp[0] = cost[0];
	dp[1] = cost[1];
	for (int i = 2; i < cost.size(); i++) {
		dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
	}
	// 注意最后一步可以理解为不用花费,所以取倒数第一步,第二步的最少值
	return min(dp[cost.size() - 1], dp[cost.size() - 2]);
}
  • 不同路径
    1
/*
不同路径:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
1.确定dp数组及下标yiyi
    dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。
2.确定递推公式
	想要求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。
    dp[i - 1][j] 表示啥,是从(0, 0)的位置到(i - 1, j)有几条路径,dp[i][j - 1]同理。
    dp[i][j] =  dp[i - 1][j] + dp[i][j - 1],因为dp[i][j]只有这两个方向过来
3.dp、数组初始化
	dp[i][0]==1,dp[0][j]==1
	for(int i=0;i<m;i++) dp[i][0] = 1;
	for(int j=0;i<n;j++) dp[0][j] = 1;
4.确定遍历顺序
	从左到右一层一层
	*/

//时间复杂度:O(m*n) 空间复杂度:O(m*n)   二维
int uniquePaths(int m, int n) {
	vector<vector<int>> dp(m, vector<int>(n, 0));
	for (int i = 0; i < m; i++) dp[i][0] = 1;
	for (int j = 0; j < n; j++) dp[0][j] = 1;
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[m - 1][n - 1];
}

//时间复杂度:O(m*n) 空间复杂度:O(n)   一维

int uniquePaths_2(int m, int n) {
	vector<int> dp(n);
	for (int i = 0; i < n; i++) dp[i] = 1;
	for (int j = 1; j < m; j++) {
		for (int i = 1; i < n; i++) {
			dp[i] += dp[i - 1];
		}
	}
	return dp[n - 1];
}

int main()
{
	cout << uniquePaths(3, 7)<<endl;
	return 0;
}

  • 不同路径 II

1对应的dp表如下:
1

  1. 确定dp数组及下标含义
    dp[i][j]:表示从(0,0)到(i,j)有dp[i][j]条不同路径
  2. 确定递推公式
if(obstacle[i][j] ==0) { dp[i][j] = dp[i-1][j]+dp[i][j-1] }
当有障碍的话就要保持初始状态,没有障碍在进行相加
  1. dp数组初始化
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

1

  1. 确定遍历顺序
    从左到右一层一层遍历
	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
			if (obstacle[i][j] == 0)
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
	}
}
/*
不同路径II:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示。

传入障碍二维数组vector<vector<int>> 
*/
int uniquePath(vector<vector<int>>& obstacle)
{
	int m = obstacle.size();
	int n = obstacle[0].size();
	vector<vector<int>> dp(m, vector<int>(n, 0));
	for (int i = 0; i < m && obstacle[i][0] == 0; i++) dp[i][0] = 1;
	for (int j = 0; j < n && obstacle[0][j] == 0; j++) dp[0][j] = 1;
	for (int i = 1; i < m; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (obstacle[i][j] == 0)
			{
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
	}
	return dp[m - 1][n - 1];
}
int main()
{
	vector<vector<int>> obs{ {0,0,0},{0,1,0},{0,0,0} };
	cout << uniquePath(obs) << endl;
	return 0;
}

  • 整数拆分
  1. 确定dp数组及含义
    dp[i]:表示拆分数字i,能够或得的最大乘积为dp[i]
  2. 确定递推公式
    其实可以从1遍历j,然后有两种渠道得到dp[i].
    一个是j * (i - j) 直接相乘。j * (i - j) 是单纯的把整数拆分为两个数相乘
    一个是j * dp[i - j],相当于是拆分(i - j),j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
    递推公式:dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
  3. dp数组初始化
    dp[2] = 1
  4. 遍历顺序
    dp[i] 是依靠 dp[i - j]的状态,所以遍历i一定是从前向后遍历,先有dp[i - j]再有dp[i]。
    枚举j的时候,是从1开始的。i是从3开始,这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
for (int i = 3; i <= n ; i++) {
	for (int j = 1; j < i - 1; j++) {
		dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
	}
}
![在这里插入图片描述](https://img-blog.csdnimg.cn/75b3ecf48dd647aab351fcf5ae3dffdd.png)

/*
整数拆分:给定一个正整数n,将其拆分为至少两个正整数的和,病史这些整数的乘积最大化。返回最大乘积

*/

int GetMultiNum(int n)
{
	vector<int> dp(n + 1);
	dp[2] = 1;
	for (int i = 3; i <= n; i++)
	{
		for (int j = 1; j < i - 1; j++)
		{
			dp[i] = max(dp[i], max(dp[i - j] * j, (i - j) * j));
		}
	}
	return dp[n];
}
int main()
{
	cout << GetMultiNum(10) << endl;
	return 0;

}
  • 不同的二叉搜索树
    0

推导:
dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
0

  1. 确定dp数组及含义
    dp[i]:表示1到i为结点组成的二叉搜索树的个数
  2. 确定递推公式
    递推关系, dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
    j相当于是头结点的元素,从1遍历到i为止
    递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量
  3. 数组初始化
    dp[0]=1
    dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0,
    也需要dp[以j为头结点左子树节点数量] = 1, 否则乘法的结果就都变成0了。
  4. 确定遍历顺序
    节点数为i的状态是依靠 i之前节点数的状态。
    那么遍历i里面每一个数作为头结点的状态,用j来遍历。
  5. 0
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= i; j++) {
		dp[i] += dp[j - 1] * dp[i - j];
	}
}
/*
不同的二叉搜索树:给定整数n,求以1,2,..n为节点组成的二叉搜索树有多少种
每个节点的左孩子都小于它,右孩子都大于它

*/
int TreesNum(int n)
{
	vector<int> dp(n + 1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			dp[i] += dp[j - 1] + dp[i - j];
		}
	}
	return dp[n];
}
int main()
{
	cout << TreesNum(5) << endl;
	return 0;
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-13 11:43:26  更:2022-09-13 11:45:30 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 21:40:18-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码