惠州模板网站建设,wordpress 翻译,网站cms系统,公关服务一、基础概念 DP的思想#xff1a; 把问题分成子问题#xff0c;前面子问题的解决结果被后面的子问题使用DP与分治法的区别#xff1a; 分治法把问题分成独立的子问题#xff0c;各个子问题能独立解决 自顶向下DP前面子问题的解决结果被后面的子问题使用#xff0c;子问题…一、基础概念 DP的思想 把问题分成子问题前面子问题的解决结果被后面的子问题使用DP与分治法的区别 分治法把问题分成独立的子问题各个子问题能独立解决 自顶向下DP前面子问题的解决结果被后面的子问题使用子问题间不相互独立 自底向上求解DP问题的步骤 1、定义状态2、状态转移 确定状态转移方程3、算法实现DP问题分类 1、线性DP2、非线性DPDP问题解决方法 顺推逆推DP可以解决的问题需满足三个条件 1、问题有最优解2、有大量子问题重复DP可以把求解的结果存起来后续用到时直接查询3、当前阶段的求解只与前面的阶段有关与之后的阶段无关 二、爬楼梯一维
假设有级楼梯每次只能爬1级或2级有多少种方法可以爬到楼梯的顶部 分析 在爬上第 i 级楼梯之前 爬楼梯的人一定站在第 i-1 级楼梯或第 i-2 级楼梯上两种情况所以爬上第 i 级楼梯的方法等于两种走法之和站在第i-1级楼梯站在第i-2级楼梯上此处涉及到应用组合数学的加法规则“或” 如果一个事件以 a 种方式发生第二个事件以 b 种不同方式发生那么存在 ab 种方式dp[i]表示爬上第i级楼梯有多少种走法 dp[1]1dp[2]2dp[i]dp[i-1]dp[i-2]i2状态转移方程 1、辅助数组
时间复杂度O(n)空间复杂度O(n)
package no1_1;
import java.util.Scanner;
public class example {public static void main(String[] args) {Scanner scnew Scanner(System.in);int nsc.nextInt();int[] dpnew int[n1];dp[1]1;dp[2]2;for(int i3;in;i) {dp[i]dp[i-2]dp[i-1];}System.out.println(dp[n]);}
}2、只使用两个变量记录前两项的值
时间复杂度O(n)空间复杂度O(1)
package no1_1;
import java.util.Scanner;
public class example {public static void main(String[] args) {Scanner scnew Scanner(System.in);int nsc.nextInt();int val11,val22,result0;;for(int i3;in;i) {//val1前一项val2当前项resultval1val2;val1val2;val2result;}System.out.println(result);}
}三、拿金币二维
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。 分析 当前位的最大金币数需要上一位也拿到最大金币数 package no1_1;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();//根据输入把金币放入数组中对应的位置int[][] goldCoins new int[n 1][n 1];for (int i 1; i n; i) {for (int j 1; j n; j) {goldCoins[i][j] scanner.nextInt();}}//该数组存储的是走到当前位置所拿的最多金币数int[][] sum new int[n 1][n 1];for (int i 1; i n; i) {for (int j 1; j n; j) {//当前位的最大金币数需要上一位也拿到最大金币数//该循环看的是sum[i][j]一直是往前走的不要被i-1和j-1误了眼觉得是倒退着走i-1和j-1只是判断上一步是应该在哪里if (sum[i][j - 1] sum[i - 1][j]) {sum[i][j] sum[i][j - 1] goldCoins[i][j];} else {sum[i][j] sum[i - 1][j] goldCoins[i][j];}}}System.out.println(sum[n][n]);}
}四、印章二维
共有n种图案的印章每种图案的出现概率相同。小A买了m张印章求小A集齐n种印章的概率。 分析 i买的印章数j凑齐的印章数dp[i][j]买了 i 个印章凑齐了 j 种的概率概率 p1 / n 情况一 i j不可能凑齐dp[i][j]0情况二 j 1买了 i 张印章凑齐的印章为图案1时概率为但有 n 种印章图案总的概率等于每个种图案的概率和应用组合数学的加法规则 即而 p 1 / n所以情况三 i j 为下面两种情况相加应用组合数学的加法规则 1、买了 i - 1 张 已经得到了 j 种最后一张随便 dp[i] [j] dp[i-1] [j] * ( j / n ) dp[i-1] [j]是买了 i - 1 张 已经得到了 j 种的概率 j / n是最后一张随便哪种的概率 2、买了 i - 1 张 只得到了 j - 1 种最后一张是第 j 种 dp[i] [j] dp[i-1] [j-1] * n-j-1 / n dp[i-1] [j-1]是买了 i - 1 张 只得到了 j - 1 种的概率 n-j-1 / n是买最后一张是第 j 种的概率 package no1_1;
import java.util.*;
public class Main {public static void main(String[] args) { Scanner scnew Scanner(System.in); int nsc.nextInt();int msc.nextInt();double[][] arraynew double[m1][n1];System.out.printf(%.4f,probability(array,n,m));//动态规划}public static double probability(double[][] array,int n,int m) {double p1.0/n;for(int i1;im;i) {//买的印章数for(int j1;jn;j) {//凑齐的印章数if(ij) {//买的印章数少于种类数不可能凑齐array[i][j]0;}else if(j1) {//只凑齐了一种array[i][j]Math.pow(p, i-1);}else {//为下面两种情况相加应用组合数学的加法规则//1、买了 i - 1 张 已经得到了 j 种最后一张随便 dp[i] [j] dp[i-1] [j] * ( j / n )//2、买了 i - 1 张 只得到了 j - 1 种最后一张是第 j 种 dp[i] [j] dp[i-1] [j-1] * (n-j1) / narray[i][j]array[i-1][j]*(j*p)array[i-1][j-1]*((n-j1)*p);}}}return array[m][n];}
}
