【算法——动态规划】蓝桥ALGO-1007 印章（C/C++）

原题链接：“蓝桥杯”练习系统

动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为较小的子问题并存储其结果来解决问题的算法思想。它通常用于解决具有重叠子问题和最优子结构性质的问题，在算法竞赛中有意想不到的惊喜。

动态规划的核心思想

动态规划的核心思想是记住已经解决的子问题，以避免重复计算。它与“分治法”相似，但不同的是，分治法通常没有子问题的重叠，而动态规划则会利用子问题的重叠特性，优化求解过程，可以理解为根据以往的经验进行此次计算操作。

动态规划的两个重要特征

1. 重叠子问题：问题可以分解为多个小的子问题，并且这些子问题在递归求解的过程中会被重复计算。例如，在求解斐波那契数列时，F(n) = F(n-1) + F(n-2)，这里的子问题 F(n-1)和F(n-2) 会不断被重复计算，因为在之前就已经把F(n-1)和F(n-2)计算出来了，就是F(n)先于F(n-1)和F(n-2)更新。 2. 最优子结构：一个问题的最优解可以通过其子问题的最优解来构造。例如，最短路径问题中的某一点到终点的最短路径，可以通过它的相邻点的最短路径来计算。

动态规划的解决步骤

1. 确定状态：通常会定义一个数组或矩阵来存储子问题的解。比如，在一个背包问题中，dp[i][j]状态可以定义为“前i件物品在容量为j的背包中的最大价值”。

2. 状态转移方程：确定如何从已知状态推导出新的状态。这一步通常被称为状态转移方程。它描述了如何利用子问题的解来构造更大问题的解。例如，斐波那契数列的状态转移方程为 F(n) = F(n-1) + F(n-2)。 3. 初始条件： 定义初始状态或边界条件。动态规划的计算通常从一些已知的基础解开始推导。例如，我们常知道斐波那契数列的初始条件是 F(0) = 0 和 F(1) = 1。

4. 计算顺序：通常可以从小规模问题开始，自底向上逐步解决子问题。通过填表法（即将子问题的解存入表格中），逐步求解最终问题的答案。

动态规划的两种实现方式

1. 自顶向下（Top-Down，记忆化递归）：通过递归的方式自上而下地解决问题，但每当需要计算一个子问题时，先检查这个子问题是否已经计算过。如果计算过，则直接取出结果，否则计算并存储结果。

2. 自底向上（Bottom-Up）：从最基本的子问题开始，逐步解决大问题。这通常通过循环来实现，直接填充动态规划的表格。

动态规划的优势

减少重复计算：通过存储子问题的解，避免了递归中的大量重复计算，提高了算法效率。 适用范围广：动态规划可以应用于各种有最优子结构和重叠子问题的场景，如最短路径、背包问题、子序列问题等。

动态规划的复杂度

动态规划的时间复杂度和空间复杂度通常取决于状态空间的大小以及状态转移方程的计算复杂度。通过优化存储结构（如滚动数组技术），空间复杂度可以从原来的 O(n²) 降低到 O(n)。在真正实战中动态规划还是非常好用的。

问题描述

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

输入格式

一行两个正整数n和m

输出格式

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

样例输入 2 3 样例输出 0.7500 数据规模和约定 1≤n，m≤20

解题思路：

这是一道动态规划题目，算是动态规划里面的入门题目。很像我们小时候集卡兑奖的游戏，我们知道当m尽量大的时候才可能集齐n种印章。特殊情况，当n>m，即：买的数量小于印章的个数，无论如何也是凑不起来的。当n<=m时，是可能凑起来n种印章的，首先每一张的概率为1/n，当需要凑齐一张印章时，买了m张，每一张都可能是那一张，所以是pow(1/n,m)*n，乘n的原因是一共n张印章，我不知道我凑齐的是哪一张所以凑得印章有n种选择。另一种就是普通的动态规划情况了，分最后一张是否重复的情况，第i-1前的都凑好了，第i张就算前面的已经取得印章，如果第i-1前的还差一张凑齐，第i张就要凑齐最后一张。状态转移方程为：a[i][j]=a[i-1][j]*(j*1.0/n)+a[i-1][j-1]*((n-j+1)*1.0/n)。

AC代码

#include<stdio.h>
#include<math.h>
int main(){
	int n,m,i,j;
	double a[25][25],p;
	scanf("%d%d",&n,&m);
	p=1.0/n;
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(i<j) a[i][j]=0;
			if(j==1){//凑齐1张的情况，所以是pow(p,i),又因为有n种，又要乘上n
				a[i][j]=pow(p,i-1);
			} 
			else{
				a[i][j]=a[i-1][j]*(j*1.0/n)+a[i-1][j-1]*((n-j+1)*1.0/n);
				//分最后一张是否重复的情况，第i-1前的都凑好了，第i张就算前面的已经取得印章
				//第i-1前的还差一张凑齐，第i张就要凑齐最后一张
			}
		}
	}
	printf("%.4f",a[m][n]);
	return 0;
} 
//动态规划问题 dp[i][j],i表示买了i张，凑齐了j种印章，

本人小白一枚，有错误的地方还望大佬指点。执笔至此，感触彼多，全文将至，落笔为终，感谢各位读者的支持.