动态规划 印章蓝桥杯 c++

本文主要是介绍动态规划 印章蓝桥杯 c++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

每一步的变化会导致其他变量的变化，多个变量在变，但每一步的变化之间是有联系的

动态规划算法的求解步骤分为：划分阶段——>确定状态和状态变量(可以从特殊情况考虑)——>找出状态转移方程——>找出递归结束条件。

动态规划一般用数组，一般用dp[i-1][j-1]来确定dp[i][j],即用上一个状态来确定当前的状态dp[i][j](逆序往回吗？貌似可以这样想)

一：有重复的：就表明前面买的 i-1 张，已经凑齐了 j 种。dp[i] [j] = dp[i-1] [j] * ( j / n ); j/n是什么意思？因为dp[i] [j]已经确定了买的第i张是重复的，所以这第i张是从前j中的任意一张都可以，要乘上概率j/n。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
//动态规划好像都用数组
double dp[25][25];
int main() {int n, m;//n种 买了m cin >> n >> m;double p = 1.0 / n;//dp[1][1]=1;for (int i = 1; i <= m; i++)//买了i种 {for (int j = 1; j <= n; j++)//要凑齐j种 {if (i < j){dp[i][j] = 0;//已经确定了不能再买了 你如果买了比n种少的肯定凑不齐 所以为0 }if (j == 1){dp[i][j] = pow((1.0 / n), (i - 1));}else{dp[i][j] = dp[i - 1][j] * (j*1.0 / n) + dp[i - 1][j - 1] * ((n - j + 1)*1.0 / n);}}}printf("%.4f", dp[m][n]);return 0;
}

这篇关于动态规划 印章蓝桥杯 c++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---