算法——动态规划（DP）——递推

我不是女神ヾ 2024-02-05 15:56 19阅读 0赞

## 一、DP ##

>  *  动态规划是一种解决多阶段决策过程中最优化问题的数学方法。**其关键思想是将复杂问题分解成简单的子问题，并利用已知的子问题的解来构建原始问题的解，从而避免重复计算和优化计算效率。**
>  *  动态规划算法通常通过填表或递推的方式来求解最优解，以减少重复计算，提高计算效率。
>  *  动态规划可以应用于诸如最短路径、最大价值、最长子序列等问题的求解。
>  *  DP与分治法的区别：
>     
>      *  分治法把问题分成独立的子问题，各个子问题能独立解决
>         
>          *  自顶向下
>      *  DP前面子问题的解决结果被后面的子问题使用，子问题间不相互独立
>         
>          *  自底向上
>  *  求解DP问题的步骤：
>     
>      *  1、定义状态
>      *  2、状态转移
>         
>          *  确定状态转移方程
>      *  3、定义初始状态
>  *  DP可以解决的问题需满足三个条件：
>     
>      *  1、问题有最优解
>      *  2、有大量子问题重复（DP可以把求解的结果存起来，后续用到时直接查询）
>      *  3、当前阶段的求解只与前面的阶段有关，与之后的阶段无关

## 二、递推 ##

>  *  递归与递推的区别
>     
>      *  递归将问题分解成更小的子问题，并通过解决这些子问题来解决原始问题。
>         
>          *  在编程中，递归函数是指在函数内部调用自身的函数。递归通常与基本情况（递归的终止条件）结合使用，以确保递归不会无限进行下去而导致栈溢出。
>      *  递推是指根据已知的初始条件以及前一项的值推导出下一项的值。
>         
>          *  递推通常用于描述数列或序列的情况，例如斐波那契数列就是一个经典的递推序列，每一项都是前两项之和。
>      *  分治算法策略主要通过递归实现；动态规划算法主要通过递推实现
>  *  递推法常被用于解决数论、组合数学、动态规划等方面的问题，比如求解斐波那契数列、阶乘、组合数等问题。使用递推法可以将复杂的问题简化，并通过寻找递推关系的规律，从而快速求解问题。

## 三、爬楼梯（一维） ##

假设有![n(1\\leq n\\leq 50)][n_1_leq n_leq 50]级楼梯，每次只能爬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的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

![3e22056f54da47b0a73a4441fd24b60e.png][]

> 分析：
> 
>  *  当前位的最大金币数，需要上一位也拿到最大金币数
>  *  ![b09ddf10046243e2b7b78fde16cf060b.jpeg][]

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

![0c2a1dca15074d61b1dc397388c53c66.png][]

> 分析：
> 
>  *  i：买的印章数
>  *  j：凑齐的印章数
>  *  dp\[i\]\[j\]：买了 i 个印章，凑齐了 j 种的概率
>  *  概率 p=1 / n
>  *  情况一：
>     
>      *  i < j
>      *  不可能凑齐，dp\[i\]\[j\]=0
>  *  情况二：
>     
>      *  j == 1
>      *  买了 i 张印章，凑齐的印章为图案1时，概率为![p^\{i\}][p_i]
>      *  但有 n 种印章图案，总的概率等于每个种图案的概率和（应用组合数学的加法规则 ）
>      *  即![p^\{i\}\\times n][p_i_times n]，而 p = 1 / n，所以
>      *  ![dp\\left \[ i \\right \]\\left \[ 1 \\right \]=(\\frac\{1\}\{n\})^\{i-1\}][dp_left _ i _right _left _ 1 _right _frac_1_n_i-1]
>  *  情况三：
>     
>      *  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];
        }
    }

## 六、过河马 ##

> ![b2af916086754ef4b63e6332703dba6d.png][]
> 
> ![64d3c458607541079712825a769c507b.png][]

> 分析：
> 
>  *  马不会走回头路的意思是：**跳的下一个点的行坐标必须大于现在的行坐标**
>  *  ![57e20024862941e5bd8ac5365c2301ea.jpeg][]
>  *

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]);
    
        }
    }

[n_1_leq n_leq 50]: https://latex.csdn.net/eq?n%281%5Cleq%20n%5Cleq%2050%29
[3e22056f54da47b0a73a4441fd24b60e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/4c949322ae324f8b96e1d53e7ee0ef6c.png
[b09ddf10046243e2b7b78fde16cf060b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/7f19eae9853645a3b114814150954038.png
[0c2a1dca15074d61b1dc397388c53c66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/e61ecc5f3ece45bf8b62cce1d7bfdf13.png
[p_i]: https://latex.csdn.net/eq?p%5E%7Bi%7D
[p_i_times n]: https://latex.csdn.net/eq?p%5E%7Bi%7D%5Ctimes%20n
[dp_left _ i _right _left _ 1 _right _frac_1_n_i-1]: https://latex.csdn.net/eq?dp%5Cleft%20%5B%20i%20%5Cright%20%5D%5Cleft%20%5B%201%20%5Cright%20%5D%3D%28%5Cfrac%7B1%7D%7Bn%7D%29%5E%7Bi-1%7D
[b2af916086754ef4b63e6332703dba6d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/0ccc778c26a64eeea883e8919fe4d854.png
[64d3c458607541079712825a769c507b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/61bf49e24dcd4e459a57e4952ac085ff.png
[57e20024862941e5bd8ac5365c2301ea.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/52277f7dbdb8430b8a318e7ff71ddb81.png