算法——动态规划（DP，Dynamic Programming）-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法——动态规划（DP，Dynamic Programming）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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级，有多少种方法可以爬到楼梯的顶部？

分析：

在爬上第 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的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

非线性dp,数据结构与算法（java版）,算法,动态规划

分析：

当前位的最大金币数，需要上一位也拿到最大金币数

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种印章的概率。

非线性dp,数据结构与算法（java版）,算法,动态规划

分析：

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-781009.html

到了这里，关于算法——动态规划（DP，Dynamic Programming）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！