DP
动态规划常用于解决优化问题。
动态规划通常以自底向上或自顶向下的方式进行求解。
自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。
自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。
动态规划算法通常通过填表或递推的方式来求解最优解,以减少重复计算,提高计算效率。
动态规划可以应用于诸如最短路径、最大价值、最长子序列等问题的求解,特别适用于解决寻找最优解或最优路径的问题,例如最长公共子序列、背包问题等。
- 求解DP问题的步骤:
- 1、定义状态
- 2、状态转移
- 确定状态转移方程
- 3、定义初始状态
- DP可以解决的问题需满足三个条件:
- 1、问题有最优解
- 2、有大量子问题重复(DP可以把求解的结果存起来,后续用到时直接查询)
- 3、当前阶段的求解只与前面的阶段有关,与之后的阶段无关
递推
- 递归与递推的区别
递归将问题分解成更小的子问题,并通过解决这些子问题来解决原始问题。
在编程中,递归函数是指在函数内部调用自身的函数。递归通常与基本情况(递归的终止条件)结合使用,以确保递归不会无限进行下去而导致栈溢出。
递推是指根据已知的初始条件以及前一项的值推导出下一项的值。
递推通常用于描述数列或序列的情况,例如斐波那契数列就是一个经典的递推序列,每一项都是前两项之和。
分治算法策略主要通过递归实现;动态规划算法主要通过递推实现
- 递推法常被用于解决数论、组合数学、动态规划等方面的问题,比如求解斐波那契数列、阶乘、组合数等问题。使用递推法可以将复杂的问题简化,并通过寻找递推关系的规律,从而快速求解问题。
二、求解斐波那契数列
public class Fibonacci {
// 计算斐波那契数列的值,使用动态规划方法
public int calculateFibonacci(int n) {
if (n <= 1) {
return n; // 当n为0或1时,直接返回n,无需计算
}
// 创建一个数组来保存中间结果,避免重复计算
int[] dp = new int[n + 1];
dp[0] = 0; // 初始化数组第一个元素为0
dp[1] = 1; // 初始化数组第二个元素为1
// 从第三个位置开始计算斐波那契数列的值
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 根据动态规划定义计算第i个斐波那契数列的值
}
return dp[n]; // 返回第n个斐波那契数列的值
}
public static void main(String[] args) {
Fibonacci fib = new Fibonacci();
int n = 10;
int result = fib.calculateFibonacci(n);
System.out.println("第 " + n + " 个斐波那契数列的值为:" + result);
}
}
三、爬楼梯(一维)
假设有级楼梯,每次只能爬1级或2级,有多少种方法可以爬到楼梯的顶部?
分析:文章来源:https://www.toymoban.com/news/detail-809063.html
- 在爬上第 i 级楼梯之前 ,爬楼梯的人一定站在第 i-1 级楼梯或第 i-2 级楼梯上,两种情况
- 所以爬上第 i 级楼梯的方法等于两种走法之和(站在第i-1级楼梯,站在第i-2级楼梯上)
- 此处涉及到应用组合数学的加法规则:(“或”)
- 如果一个事件以 a 种方式发生,第二个事件以 b 种(不同)方式发生,那么存在 a+b 种方式
- dp[i]表示爬上第i级楼梯有多少种走法
- dp[1]=1
- dp[2]=2
- dp[i]=dp[i-1]+dp[i-2],i>2(状态转移方程)
1、辅助数组
时间复杂度O(n),空间复杂度O(n)
package no1_1;
import java.util.Scanner;
public class example {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] dp=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;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 sc=new Scanner(System.in);
int n=sc.nextInt();
int val1=1,val2=2,result=0;;
for(int i=3;i<=n;i++) {//val1:前一项;val2:当前项
result=val1+val2;
val1=val2;
val2=result;
}
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 种的概率
- 概率 p=1 / 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 sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
double[][] array=new double[m+1][n+1];
System.out.printf("%.4f",probability(array,n,m));//动态规划
}
public static double probability(double[][] array,int n,int m) {
double p=1.0/n;
for(int i=1;i<=m;i++) {//买的印章数
for(int j=1;j<=n;j++) {//凑齐的印章数
if(i<j) {//买的印章数少于种类数,不可能凑齐
array[i][j]=0;
}else if(j==1) {//只凑齐了一种
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-j+1) / n
array[i][j]=array[i-1][j]*(j*p)+array[i-1][j-1]*((n-j+1)*p);
}
}
}
return array[m][n];
}
}
六、过河马
分析:
- 马不会走回头路的意思是:跳的下一个点的行坐标必须大于现在的行坐标
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
long[][] methods=new long[102][102];//methods[i] [j] 表示马从(1,1)跳到(i,j)的走法种数。
int i,j;
//初始状态
methods[1][1]=0;
methods[2][3]=1;
methods[3][2]=1;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(i-2>=1&&j-1>=1){
methods[i][j]+=methods[i-2][j-1];//马从(i-2,j-1)跳到(i,j),则点(i,j)的走法加上(i-2,j-1)的走法数
methods[i][j]%=1000000007;//每次更新methods的值时,都进行取余运算,如果全部运算完再做取余运算,数字容易溢出
}
if(i-1>=1&&j-2>=1){
methods[i][j]+=methods[i-1][j-2];//马从(i-1,j-2)跳到(i,j)
methods[i][j]%=1000000007;
}
if(i-1>=1&&j+2<=m){
methods[i][j]+=methods[i-1][j+2];//马从(i-1,j+2)跳到(i,j)
methods[i][j]%=1000000007;
}
if(i-2>=1&&j+1<=m){
methods[i][j]+=methods[i-2][j+1];//马从(i-2,j+1)跳到(i,j)
methods[i][j]%=1000000007;
}
}
}
//methods[n][m]表示马从(1,1)到(n,m)点的走法数
System.out.println(methods[n][m]);
}
}
七、进击的青蛙
分析:
- 跟爬楼梯的题目类似,照着写,然后根据题目的具体要求再修改一下即可
- BufferedReader类相对于 Scanner 类,这种方法会占用更少的内存,特别是在处理大量输入时。
- 该题如果用Scanner,只能拿20分,内存超限
package no1_1;
import java.io.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());//读取一整行的字符串,然后转成int类型
int MOD = 1000000007;
long[] dp = new long[n+1];//dp数组先用来存石头,然后覆盖着存储到达该的方法数,(省点内存)
for(int i = 1; i <= n; i++) {
dp[i] = Integer.parseInt(reader.readLine());
}
//初始化
dp[1] = (dp[1] == 0) ? 1 : 0;
dp[2] = (dp[2] == 0) ? dp[1] + 1 : 0;
dp[3] = (dp[3] == 0) ? dp[1] + dp[2] + 1 : 0;
for (int i = 4; i <= n; i++) {
if (dp[i] == 1) {//该点有石头,无法到达
dp[i] = 0;
} else {//每次更新dp的方法数时,都要取余
dp[i] = (dp[i-1]% MOD + dp[i-2]% MOD + dp[i-3]% MOD) % MOD;
}
}
if(dp[n]==0) {//无法到达
System.out.println("No Way!");
}else {//输出到达该点的方法数
System.out.println(dp[n]);
}
}
}
文章来源地址https://www.toymoban.com/news/detail-809063.html
到了这里,关于算法——动态规划(DP)——递推的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!