上海网站工作室,电子商务网站开发,麻将棋牌网站开发,网站投稿系统怎么做文章目录 动态规划的定义动态规划的核心思想青蛙跳阶问题解法一#xff1a;暴力递归解法二#xff1a;带备忘录的递归解法#xff08;自顶向下#xff09;解法三#xff1a;动态规划#xff08;自底向上#xff09; 动态规划的解题套路什么样的问题考虑使用动态规划暴力递归解法二带备忘录的递归解法自顶向下解法三动态规划自底向上 动态规划的解题套路什么样的问题考虑使用动态规划动态规划的解题思路 第14届JavaB组蓝桥杯“蜗牛”问题 动态规划的定义
动态规划Dynamic programming简称 DP是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。 ”dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.“ 动态规划就是给定的一个问题拆成一个个子问题直到子问题可以直接解决。把子问题答案保存起来以减少重复计算。再根据子问题答案反推得出原问题解的一种方法。
动态规划的核心思想
拆分子问题记住过往减少重复运算。
体现该思想的例子 A “11111111 ”A “上面等式的值是多少”B 计算 “8”A : 在上面等式的左边写上 “1” 呢A : “此时等式的值为多少”B : 很快得出答案 “9”A : “你怎么这么快就知道答案了”A : “只要在8的基础上加1就行了”A : “所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 ‘记住求过的解来节省时间’” 青蛙跳阶问题 问题一只青蛙一次可以跳上1级台阶也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。 问题分析 到达第10级可以从第9级跳1级台阶也可以从第8级跳2级台阶。 到达第9级可以从第8级跳1级台阶也可以从第7级跳2级台阶。 到达第8级可以从第7级跳1级台阶也可以从第6级跳2级台阶。 定义f(n)为跳到第n级台阶 f10 f9f(8)
f (9) f(8) f(7)
f (8) f(7) f(6)
...
f(3) f(2) f(1)即通用公式为: f(n) f(n-1) f(n-2)当只有2级台阶时有两种跳法第一种是直接跳两级第二种是先跳一级然后再跳一级。即f(2) 2;当只有1级台阶时只有一种跳法即f(1) 1
解法一暴力递归
class Solution {public int Ways(int n) {if(n 1){return 1;}if(n 2){return 2;}return Ways(n-1) Ways(n-2);}
}时间复杂度
一个子问题时间 fn-1fn-2也就是一个加法的操作所以复杂度是 O(1)问题个数 递归树节点的总数 2n-1所以是复杂度O(2n)。
总结
时间复杂度是指数级别爆炸式增长容易超时。存在大量重复计算。
改进措施: 使用备忘录将计算过的答案存下来。省去重复计算的耗时。
解法二带备忘录的递归解法自顶向下
一般使用一个数组或者一个map集合充当备忘录。 static MapInteger,Integer mapnew HashMap();private static int ways2(int n) {if(n1) return 1;if(n2) return 2;if(map.containsKey(n)) {return map.get(n);}else {map.put(n,(ways(n-1)ways(n-2)));return ways(n-1)ways(n-2);}}时间复杂度
子问题个数树节点数n解决一个子问题还是O(1),所以带备忘录的递归算法的时间复杂度是O(n)。
解法三动态规划自底向上
动态规划和带备忘录的递归解法基本思想是一致的都是减少重复计算时间复杂度也都是差不多。 带备忘录的递归是从f(10)往f(1)方向延伸求解的所以也称为自顶向下的解法。动态规划从较小问题的解由交叠性质逐步决策出较大问题的解它是从f(1)往f(10方向往上推求解所以称为自底向上的解法。 动态规划有几个典型特征最优子结构、状态转移方程、边界、重叠子问题。 在青蛙跳阶问题中 f(n-1)和f(n-2) 称为 f(n) 的最优子结构f(n) f(n-1)f(n-2) 称为状态转移方程f(1) 1, f(2) 2 是边界比如f(10) f(9)f(8),f(9) f(8) f(7) ,f(8)是重叠子问题。 我们来看下自底向上的解法从f(1)往f(10方向一个for循环就可以解决 private static int ways(int n) {if(n1) return 1;if(n2) return 2;int a1,b2,temp0;for(int i3;in;i) {tempab;ab;btemp;}return temp;}动态规划的解题套路
什么样的问题考虑使用动态规划
如果一个问题可以把所有可能的答案穷举出来并且穷举出来后发现存在重叠子问题就可以考虑使用动态规划。 比如一些求最值的场景如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等都是动态规划的经典应用场景。 动态规划的解题思路
动态规划的核心思想就是拆分子问题记住过往减少重复计算。 并且动态规划一般都是自底向上的动态规划的思路如下 穷举分析确定边界找出规律确定最优子结构写出状态转移方程 ★ 一道动态规划问题其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质。 第14届JavaB组蓝桥杯“蜗牛”问题 问题描述 这天一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴底部纵坐标为 0横坐标分别为 x1, x2,…, xn。竹竿的高度均为无限高宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x轴上或者竹竿上爬行在 x 轴上爬行速度为 1 单位每秒由于受到引力影响蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和1.3 单位每秒。 为了快速到达目的地它施展了魔法在第 i 和 i 1 根竹竿之间建立了传送门0 i n如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)就可以瞬间到达第 i 1 根竹竿的高度为 bi1 的位置 (xi1,bi1)请计算蜗牛最少需要多少秒才能到达目的地。 输入格式 输入共 1 n 行第一行为一个正整数 n 第二行为 n 个正整数x1, x2, . . . , xn 后面 n − 1 行每行两个正整数 ai , bi1。 输入格式
3
1 10 11
1 1
2 1输出格式
4.20样例说明 (0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0)花费时间为 11/0.701/1.31 ≈ 4.20 评测用例规模与约定 对于 20% 的数据保证 n ≤ 15 对于 100% 的数据保证 n ≤ 105ai , bi ≤ 104xi ≤ 109 问题分析 每根竹竿有两个出发点从最底部出发和从传送门出发。自底而上每次选取最短的路径。
采用动态规划
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);//输入有几根竹竿int n sc.nextInt();//将n个竹竿的横坐标存放在一个数组gan中.//为了方便0舍弃不用int[] gan new int[n 1];for (int i 1; i n; i) {gan[i] sc.nextInt();}//存放每个下标对应竹竿的传送门位置 aiint[] a new int[n 1];//存放每个下标对应的传送到的位置 bi1int[] b new int[n 1];//为了方便0舍弃不用。最后一根竹竿不需要设置传送门afor (int i 1; i n; i) {a[i] sc.nextInt();b[i 1] sc.nextInt();}//新建一个二维数组用来存放从每个竹竿有两个出发点出发,同样舍弃[0][0],[0][1]不用double[][] dp new double[n 1][2];//第一根竹竿出发点有两个dp[1][0] gan[1];dp[1][1] gan[1] a[1] / 0.7;//每行二维数组的第一个数存放从上一根竹竿的两个出发点出发到达这根竹竿底部的路径长短// 第二个数存放从上一根竹竿的两个出发点出发到达这根竹竿传送门的路径长短for (int i 2; i n 1; i) {dp[i][0] Math.min((dp[i - 1][0] gan[i] - gan[i - 1]), (dp[i - 1][1] b[i] / 1.3));//如果此竹竿的传送门比传送过来的位置高则第二种出发点需要往上爬 对应/0.7if (a[i] b[i]) {dp[i][1] Math.min((dp[i - 1][0] gan[i] - gan[i - 1] a[i] / 0.7), (dp[i - 1][1] (a[i] - b[i]) / 0.7));} else {dp[i][1] Math.min((dp[i - 1][0] gan[i] - gan[i - 1] a[i] / 0.7), (dp[i - 1][1] (b[i] - a[i]) / 1.3));}}System.out.printf(%.2f, dp[n][0]);}
}
