首页 > 其他分享 >动态规划·爬楼梯问题(一维)与印章问题(二维)

动态规划·爬楼梯问题(一维)与印章问题(二维)

时间:2024-03-17 11:59:59浏览次数:19  
标签:概率 爬楼梯 int double 印章 二维 一维 include dp

算法介绍

动态规划(Dynamic Programming)的核心是当前状态的解由上一状态得到。算法将求解问题分解成多个相似的子问题,每个子问题的解由上一个子问题的解得到并储存,往往用于优化递归问题,减少相同子问题的重复计算。

一维动态规划·爬楼梯问题

问题描述

假设你正在爬楼梯,需要 n 阶你才能到达楼顶,每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

示例 1:

输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2:

输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

算法分析

爬n阶楼梯的上一个状态是已经爬了n-1阶楼梯,再爬1阶到了n阶,或者是已经爬了n-2阶楼梯,再爬2阶到了n阶。所以爬到n阶楼梯所有方法数等于爬n-1阶楼梯的解+爬n-2阶楼梯的解。而爬n-1阶楼梯的解又等于n-2阶的解+n-3阶的解......可以看到这是一个递归问题,但用传统递归方法去算,n-2阶的解便会被重复计算,当处理数据过大时,算法效率明显降低。

因此我们使用动态规划的思维创建一个动态规划数组dp来保存每个状态的解,并由该解推出下一个状态的解,这样每个解只需要计算一次,时间效率明显提升。

我们观察到该题只有一个变量n,因此只需要创建一个一维数组dp[],dp[n] = dp[n-1] + dp[n-2]。

代码实现(C语言)

//动态规划
#include "stdio.h"
#include "stdlib.h"
int main()
{
    int n,i,*dp;
	scanf("%d",&n);
	dp=(int *)malloc(sizeof(int)*n);//动态内存数组,也可以根据题设n最大值用静态数组
	dp[1]=1,dp[2]=2;
	for(i=3;i<=n;i++)
		dp[i]=dp[i-1]+dp[i-2];
	printf("%d",dp[n]);
	return 0;
}

我们注意到递推过程中实际上只有最新创建的3个数组空间被利用,而此前计算的数据只使用了一次就没用了,我们可以用滚动数组3个变量来优化。

//滚动数组
#include "stdio.h"
int main()
{
    int n;
	scanf("%d",&n);
	int a=1,b=2,c=n;
	while(n-->=3)
	{
		c=a+b;
		a=b;
		b=c;
	}
	printf("%d",c);
	return 0;
}

二维动态规划·印章问题

问题描述

共有n种图案的印章,每种图案的出现概率相同。小A买了m张印章,求小A集齐n种印章的概率。

输入格式

  一行两个正整数n和m

输出格式

  一个实数P表示答案,保留4位小数。

样例输入

2 3

样例输出

0.7500

数据规模和约定

  1≤n,m≤20

算法分析

买m张印章集齐n种不同印章的上一状态是买m-1张集齐了n-1种,第m张为不同的,或者买m-1张时就已经集齐了n种,第m张为重复的。即买了m张有n张不同印章的概率为买m-1张时有n-1张不同印章,第m张为不同的的概率+买m-1张时有n张不同印章,第m张为n张中的一张的概率。而这两种情况又可以继续往下分。

这是一个递归问题,如果使用纯数学计算概率的思路用传统递归也能解:

//传统递归
#include "stdio.h"
#include "math.h"
double f(double x,double y);//x为已经买到了x种不同的印章,y为买到的第y个印章
double n,m;
int main() 
{
	scanf("%lf %lf",&n,&m);
	printf("%.4lf",f(0,1));
	return 0;
}
double f(double x,double y)
{
	if(y>m && x<n)
		return 0;
	if(x<n)
		return (n-x)/n*f(x+1,y+1)+x/n*f(x,y+1);
	/*数学概率统计
	在m次购买得到n种印章的成功情况下,
	第y次买到新印章和第y次买到重复印章的概率*/
	else
		return 1;
}

但深度递归在处理较大数据时时间效率很低很低,在n=10,m=30时就开始不行了,而动态规划算法在m=300时依然秒出结果。

因此我们看动态规划的思路,把每一种状态记录,然后用这一状态的数据计算出下一状态的解。

假设n为4,m为6,总共4种不同印章。

创建二维动态规划数组dp[][],

记子状态为dp[i][j],买了i张,有j种不同印章的概率(i=0和j=0的空间就不用了)。列表(打表)如下:

每种状态的概率j
1234
i11000
200
30
4
5
6

容易知道,只买1张,不可能有两张不同印章,即当 j>i 时概率为0;只买一张,这一张一定是新的,概率为1;买两张,却只获得一张新的(总共有4种不同印章),两张是重复的概率为

(\tfrac{1}{4})*(\tfrac{1}{4})*4

即 (\tfrac{1}{n})^{i-1},可以看出 i=1 也满足公式,所以当 j=1 时,该子状态出现的概率为 (\tfrac{1}{n})^{i-1},即dp[i][1]=(\tfrac{1}{n})^{i-1}

当 i>j 时,dp[i][j]=dp[i-1][j-1]*第i张买到新印章的概率 + dp[i-1][j]*第i张买到重复印章的概率,即

dp[i][j]=dp[i-1][j-1]* \tfrac{1}{n}*(n-(j-1))+dp[i-1][j]*\tfrac{1}{n}*j

代码实现(C语言)

//动态规划
#include "stdio.h"
#include "math.h"
int main()
{
	int n,m,i,j;
	scanf("%d %d",&n,&m);
	/*也可以用动态内存二维数组,引入头文件"stdlib.h"
	double p=1.0/n,**dp=(double **)malloc(sizeof(double*)*(m+1));
	for(i=1;i<=m+1;i++)
		dp[i]=(double *)malloc(sizeof(double)*(n+1));
	*/
	double p=1.0/n,dp[21][21];
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(i<j)
				dp[i][j]=0;
			else if(j==1)
				dp[i][j]=pow(p,i-1);
			else
				dp[i][j]=dp[i-1][j]*p*j+dp[i-1][j-1]*p*(n-(j-1));
	printf("%.4lf",dp[m][n]);
	return 0;
}

列表时也可以用买了j张作列,获得i种不同印章作行,代码条件条件判断稍微变换即可:

还是n=4,m=6,

//动态规划
#include "stdio.h"
#include "math.h"
int main()
{
	int m,n,i,j;
	scanf("%d%d",&n,&m);
	double p=1.0/n,dp[21][21];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(i>j)
				dp[i][j]=0;
			else if(i==1)
				dp[i][j]=pow(p,j-1);
			else
				dp[i][j]=dp[i][j-1]*p*i+dp[i-1][j-1]*p*(n-(i-1));
	printf("%.4lf",dp[n][m]);
	return 0;
}

标签:概率,爬楼梯,int,double,印章,二维,一维,include,dp
From: https://blog.csdn.net/SparkHC0618/article/details/136772547

相关文章

  • 二维前缀和知识讲解+例题
    1.二维前缀和二维前缀和是一种数组处理技术,它在处理二维数据(如矩阵)时非常有用。它的概念源自于一维前缀和,但扩展到了两个维度。二维前缀和的主要思想是将矩阵中的每个元素与其上方和左方的元素进行累加,从而快速计算出矩阵中任意子矩阵的元素和。定义如下:设有一个二维矩阵......
  • 节点异常检测-二维高斯分布
    所以一个样本是一个椭圆曲线吗?不完全是这样。在二维高斯分布的上下文中,单个样本是分布中的一个点,而不是一个椭圆曲线。椭圆曲线实际上表示的是等高线,也就是概率密度函数在不同值下的轮廓线。每条椭圆曲线上的点具有相同的概率密度,这些椭圆反映了数据的分布特性,如集中趋势和变异情......
  • Java中二维数组全部赋成同一个值
    有以下几种方法可以将二维数组全部赋成同一个值:1. 使用双重循环遍历二维数组,逐个元素赋值。int[][]arr=newint[3][3];intvalue=5;for(inti=0;i<arr.length;i++){for(intj=0;j<arr[i].length;j++){arr[i][j]=value;}}2. 使用Arrays.......
  • 动态规划背包问题(01、二维、完全背包)
    背包问题01背包dfs#include<bits/stdc++.h>usingnamespacestd;constintN=1009;intn,m,v[N],w[N];intdfs(intx,intspV){//当前枚举到哪个物品,背包剩余容量 if(x>n)return0; elseif(spV<v[x])returndfs(x+1,spV); elsereturnmax(dfs(x+1,spV),dfs(x+......
  • 二维逆运动学 – 代码
    介绍在本系列的前一部分中,我们讨论了具有两个自由度的机械臂的反向运动学问题;如下图所示。在这种情况下,机械臂的长度和 通常是已知的。如果我们必须到达的点是 ,那么配置就变成了一个三角形,其中所有边都是已知的。然后,我们推导出了角度和的方程,它控制着机械臂关节的旋转:(1......
  • 稀疏数组与二维数组之间的转换
    稀疏数组介绍:稀疏数组:当一个数组中大部分元素为同一个值时,就可以考虑使用稀疏数组来保存数据节省空间。稀疏数组的原理:1)稀疏数组一共三列,第一行的第一列保存原二维数组的行数,第一行第二列保存原二维数组的列数,第一行第三列保存原二维数组非0数据的个数;2)稀疏数组一共有【原二维......
  • 二维逆运动学 – 数学
    如果您已经关注此博客一段时间,您可能已经注意到一些反复出现的主题。逆向运动学绝对是其中之一,我已经专门写了一整套关于如何将其应用于机械臂和触手的系列文章。如果您还没有读过它们,请不要担心:这个新系列将是独立的,因为它从一个新的角度回顾了逆运动学的问题。您可以在此处阅......
  • 一维数组_校门外的树
    任务描述某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表......
  • 一维时间序列的离散正交Stockwell变换和离散余弦Stockwell变换
    MATLAB环境下一维时间序列信号的离散正交Stockwell变换和离散余弦Stockwell变换。Stockwell变换是一种对短时傅立叶变换STFT和小波变换WT扩展的时频分析方法。Stockwell变换将傅里叶变换的绝对相位保持特性与WT的频率相关分析和多分辨率特性结合起来。离散正交Stockwell变换......
  • LeetCodeHot100 73. 矩阵置零 54. 螺旋矩阵 48. 旋转图像 240. 搜索二维矩阵 II
    73.矩阵置零https://leetcode.cn/problems/set-matrix-zeroes/description/?envType=study-plan-v2&envId=top-100-likedpublicvoidsetZeroes(int[][]matrix){inttop=0,bottom=matrix.length,left=0,right=matrix[0].length;int[][]flag......