实验二动态规划算法
一．问题描述
小明想要在王者荣耀游戏里晋升一个段位，假设他一共需打了
场比赛，且必须成功赢得至少70的场次才能成功晋升。假设每场比赛小明获胜的概率分别为p1，p2，…，p
，请帮他算出成功晋级段位的概率是多少？
输入：参数1：整数
um（0
um1000），表示比赛的场数。参数2：整数数组p
ump1，p2，…，p
um，其中pi表示小明有pi的概率赢得第i场比赛。（0pi100）
输出：成功晋级段位的概率，保留小数点后5位，最后结果四舍五入。
二．实验目的及要求
1理解动态规划法的设计思想2掌握动态规划法的求解步骤3掌握用动态规划法解题的算法框架
三．实验分析1分析问题的最优子结构
fij表示在i场比赛中ji，小明一共能赢得j场比赛的概率；
fij的最优解所包含的fi1j和fi1j1也是最优的。说明问题的最优解包含着其子问题的最优解，满足最优子结构性质。
2建立递归关系
f特别的，当i0时有如下公式：
由此递推求出所有的fi，j，所求概率为：m7
10向上取整
四．算法伪代码或流程图
fori←1to
umdodpi0dpi101pi1forj←1to
umdodpijdpi1j1pi1dpi1j1pi1forilowto
umdopassdp
umi
五．算法时间复杂性分析
算法的时间复杂度是O
2
六．问题思考与总结
（1）动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的；
（2）动态规划是针对一类求最优解的问题的算法，其核心是将一个问题分解成为若干个子问题部分类似于分治的思想（不懂得可以参考归并排序），通过求每一次的最优决策，来得到一个最优解。在这里最重要的就是子
f问题的思想；（3）动态规划解题步骤：Step1：描述最优解的结构特征Step2：递归地定义一个最优解的值Step3：自底向上计算一个最优解的值Step4：从已计算的信息中构造一个最优解
七．实验中出现的问题及总结
（1）在导入老师给的工程文件导入eclipse时出现错误，最后经过改写mai
函数的测试类，重新建了一个工程文件；
（2）动态规划算法通常用于求解具有某种最优性质的问题；（3）问题的最优子结构性质是该问题可用动态规划算法求解的显著特征；
运行结果：
fr