• 样本对应模型例题

    求两字符串的最长公共子序列

    • [[最长子序列]]
    • 子序列可以不连续，子串必须连续
    • 思路：样本对应模型先把数组对应成dp表，填basecase。找普遍的位置依赖
    • process（i，j）表示arr[i]，buf[j]之前最长的公共子序列。此时可能以arr[i]结尾，以buf结尾，不以这两端结尾，同时以两端结尾

    最短路径和问题

    • 题目：从二位数组在左上走到右下，只能向左，下走
    • 思路：从最下行的右往左填。每次选min（右，下）
    • 优化：因为每个位置依赖本行和下行->两行数组
    • 优化：因为每个位置依赖的本行右侧不回退，所以只用一行，右边直接覆盖即可
    •     package class21;
    
    public class Code01_MinPathSum {
    
    	public static int minPathSum1(int[][] m) {
    		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
    			return 0;
    		}
    		int row = m.length;
    		int col = m[0].length;
    		int[][] dp = new int[row][col];
    		dp[0][0] = m[0][0];
    		for (int i = 1; i < row; i++) {
    			dp[i][0] = dp[i - 1][0] + m[i][0];
    		}
    		for (int j = 1; j < col; j++) {
    			dp[0][j] = dp[0][j - 1] + m[0][j];
    		}
    		for (int i = 1; i < row; i++) {
    			for (int j = 1; j < col; j++) {
    				dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
    			}
    		}
    		return dp[row - 1][col - 1];
    	}
    
    	public static int minPathSum2(int[][] m) {
    		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
    			return 0;
    		}
    		int row = m.length;
    		int col = m[0].length;
    		int[] dp = new int[col];
    		dp[0] = m[0][0];
    		for (int j = 1; j < col; j++) {
    			dp[j] = dp[j - 1] + m[0][j];
    		}
    		for (int i = 1; i < row; i++) {
    			dp[0] += m[i][0];
    			for (int j = 1; j < col; j++) {
    				dp[j] = Math.min(dp[j - 1], dp[j]) + m[i][j];
    			}
    		}
    		return dp[col - 1];
    	}
    
    	// for test
    	public static int[][] generateRandomMatrix(int rowSize, int colSize) {
    		if (rowSize < 0 || colSize < 0) {
    			return null;
    		}
    		int[][] result = new int[rowSize][colSize];
    		for (int i = 0; i != result.length; i++) {
    			for (int j = 0; j != result[0].length; j++) {
    				result[i][j] = (int) (Math.random() * 100);
    			}
    		}
    		return result;
    	}
    
    	// for test
    	public static void printMatrix(int[][] matrix) {
    		for (int i = 0; i != matrix.length; i++) {
    			for (int j = 0; j != matrix[0].length; j++) {
    				System.out.print(matrix[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    
    	public static void main(String[] args) {
    		int rowSize = 10;
    		int colSize = 10;
    		int[][] m = generateRandomMatrix(rowSize, colSize);
    		System.out.println(minPathSum1(m));
    		System.out.println(minPathSum2(m));
    
    	}
    }
    

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48
      • 49
      • 50
      • 51
      • 52
      • 53
      • 54
      • 55
      • 56
      • 57
      • 58
      • 59
      • 60
      • 61
      • 62
      • 63
      • 64
      • 65
      • 66
      • 67
      • 68
      • 69
      • 70
      • 71
      • 72
      • 73
      • 74
      • 75
      • 76
      • 77
      • 78
      • 79
      • 80

    K步超出矩阵概率

    • 题目：人在（row，col）走k步求超出[N][M]矩阵的概率。中途超出也算
    • 思路：当前位置直接调往四周走，K-1的情况。最后获得不超出的次数。总次数为4^k。
    • base case：只要当前坐标超出[N][M]直接返回-1，上层处理-1的情况
    • 传入：（row，col），K
    • 决策：往四周走
    • 传出：（row，col），K
    • dp：有三个参数需要改三维dp类似 [[象棋跳马问题]]，k为层数
    • 预处理：0层的，[M][N]都填一
    • 普遍位置依赖 dpk-1层的四周位置
    • 代码
    •     public static double livePosibility2(int row, int col, int k, int N, int M) {
    		long[][][] dp = new long[N][M][k + 1];
    		for (int i = 0; i < N; i++) {
    			for (int j = 0; j < M; j++) {
    				dp[i][j][0] = 1;
    			}
    		}
    		for (int rest = 1; rest <= k; rest++) {
    			for (int r = 0; r < N; r++) {
    				for (int c = 0; c < M; c++) {
    					dp[r][c][rest] = pick(dp, N, M, r - 1, c, rest - 1);
    					dp[r][c][rest] += pick(dp, N, M, r + 1, c, rest - 1);
    					dp[r][c][rest] += pick(dp, N, M, r, c - 1, rest - 1);
    					dp[r][c][rest] += pick(dp, N, M, r, c + 1, rest - 1);
    				}
    			}
    		}
    		return (double) dp[row][col][k] / Math.pow(4, k);
    	}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19

    人杀死怪兽的概率

    • 题目：人发动K次攻击，每次打击[0~M]等概率的血。怪的血量为N
    • 思路：每次攻击都枚举[0~M]攻击，往后传k–，M，n-相应的值。统计怪没死的次数。all=（M+1）^K
    • 传入：K，M，N
    • base case：N<=0 retuen 0，k=0&&N>0 return 1
    • 决策：对当前的K，M，N，枚举0~M的伤害值。接收每次调用的返回值，汇总后网上传
    • 传出：枚举行为调用相应的KMN
    • dp：这里有枚举行为所以要建严格的表结构处理依赖，只需要建立（K，N）的表
    • 预处理：（这里不好在格中填存活的次数，所以填死亡的次数），N=0列的死亡次数等于m^K
    • 普遍位置依赖：dp[k-1][n-0]~dp[k-1][n-m]，（n-m>=1）

    代码

         		  public static double dp2(int N, int M, int K) {
     		  		if (N < 1 || M < 1 || K < 1) {
     		  			return 0;
     		  		}
     		  		long all = (long) Math.pow(M + 1, K);
     		  		long[][] dp = new long[K + 1][N + 1];
     		  		dp[0][0] = 1;
     		  		for (int times = 1; times <= K; times++) {
     		  			dp[times][0] = (long) Math.pow(M + 1, times);
     		  			for (int hp = 1; hp <= N; hp++) {
     		  				dp[times][hp] = dp[times][hp - 1] + dp[times - 1][hp];
     		  				if (hp - 1 - M >= 0) {
     		  					dp[times][hp] -= dp[times - 1][hp - 1 - M];
     		  				} else {
     		  					dp[times][hp] -= Math.pow(M + 1, times - 1);
     		  				}
     		  			}
     		  		}
     		  		long kill = dp[K][N];
     		  		return (double) ((double) kill / (double) all);
     		  	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    给定一个正数求裂开的方法数

    • 题目：把一个正数才成其他正数，求组合
      • 给定一个正数1，裂开的方法有一种，(1) 给定一个正数2，裂开的方法有两种，(1和1)、(2) 给定一个正数3，裂开的方法有三种，(1、1、1)、(1、2)、(3) 给定一个正数4，裂开的方法有五种，(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、 (4)
        给定一个正数n，求裂开的方法数。
    • 思路：两个参数，上一个裂出来的数pre，还剩的数rest。rest枚举所有减去pre的情况，因为相同值的算一个数（不用全排列），所以pre从小加到大
    • 传入：pre，rest
    • base case：rest-pre=0时 return 1；rest-pre<0 时 return 0；
    • 决策：枚举rest减去所有次数的pre的情况
    • 传出：newPre，newRest

    • 代码

      ```java
		  public static int dp1(int n) {
		  		if (n < 0) {
		  			return 0;
		  		}
		  		if (n == 1) {
		  			return 1;
		  		}
		  		int[][] dp = new int[n + 1][n + 1];
		  		for (int pre = 1; pre <= n; pre++) {
		  			dp[pre][0] = 1;
		  			dp[pre][pre] = 1;
		  		}
		  		for (int pre = n - 1; pre >= 1; pre--) {
		  			for (int rest = pre + 1; rest <= n; rest++) {
		  				int ways = 0;
		  				for (int first = pre; first <= rest; first++) {
		  					ways += dp[first][rest - first];
		  				}
		  				dp[pre][rest] = ways;
		  			}
		  		}
		  		return dp[1][n];
		  	}
```

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
    • 存在枚举行为，所以可以用严格的表结构来优化（pre，rest）建表
    • 普遍位置的表依赖：一条斜线，找到能某个已经计算过部分斜线的格子
    • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uHf0JsYg-1663668124568)(…/assets/image_1641963812307_0.png)]
         public static int dp2(int n) {
     		if (n < 0) {
     			return 0;
     		}
     		if (n == 1) {
     			return 1;
     		}
     		int[][] dp = new int[n + 1][n + 1];
     		for (int pre = 1; pre <= n; pre++) {
     			dp[pre][0] = 1;
     			dp[pre][pre] = 1;
     		}
     		for (int pre = n - 1; pre >= 1; pre--) {
     			for (int rest = pre + 1; rest <= n; rest++) {
     				dp[pre][rest] = dp[pre + 1][rest];
     				dp[pre][rest] += dp[pre][rest - pre];
     			}
     		}
     		return dp[1][n];
     	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
  • 相关阅读:
    python笔记之面向对象
    家庭个人服务器的搭建之路--非傻瓜式描述
    Tekla添加零件ContourPlate
    关于torch.dist(p=2)和nn.MESLoss的区分
    Navicat 使用教程
    K8S自动化运维容器Docker集群
    基于微信公众号的图书借阅平台设计与实现
    【EdgeX（15）】 ：在EdgeX环境下配置eKuiper规则引擎服务，配置规则处理device-virtual发送的数据，并转发给HTTP服务
    Vue3最佳实践 第六章 Pinia,Vuex与axios,VueUse 1（Pinia）
    每日一练 | 华为认证真题练习Day119
  • 原文地址：https://blog.csdn.net/PaintD/article/details/126958608