牛可动态规划--2025（4）题

1.最大正方形的题packagefushi.zhenti.shangji.dongtaiguihua;importjava.util.Scanner;publicclassshuzhengfangxing{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();sc.nextLine();char[][]gridnewchar[n][m];for(inti0;in;i){Stringssc.nextLine();grid[i]s.toCharArray();}intresultMaxZ(grid);System.out.println(result);sc.close();}//寻找最大的正方形privatestaticintMaxZ(char[][]grid){// 判空if(gridnull||grid.length0||grid[0].length0){return0;}intngrid.length;// 行数intmgrid[0].length;// 列数int[][]dpnewint[n][m];//用来保存正方形数量的矩阵inttotal0;//此题的核心来了。计算最大正方形需要计算每次for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]1){//位于第一行或者第一列只有一个正方形if(i0||j0){dp[i][j]1;}else{//寻找这里能成为的最大正方形数量,//1 1//1 1 左 上左上dp[i][j]Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])1;}totaltotaldp[i][j];}else{dp[i][j]0;}}}returntotal;}}2.类似题目之–牛客网 矩阵最短路径最小路径和对应题号NC59 / NC10575packagefushi.zhenti.shangji.dongtaiguihua;importjava.util.Scanner;publicclasszuiduanlujinhe{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 输入行数 m 列数 nintmsc.nextInt();intnsc.nextInt();int[][]gridnewint[m][n];for(inti0;im;i){for(intj0;jn;j){grid[i][j]sc.nextInt();}}// 计算并输出结果intresminPathSum(grid);System.out.println(res);sc.close();}privatestaticintminPathSum(int[][]grid){if(gridnull||grid.length0||grid[0].length0)return0;intmgrid.length;intngrid[0].length;int[][]dpnewint[m][n];dp[0][0]grid[0][0];//grid//1 1//1 1//dp//1 2//2 3//先弄第一行第一行的每个元素的最短路径for(inti1;im;i){//注意i1 不越界dp[0][i]grid[0][i]dp[0][i-1];}for(inti1;in;i){dp[i][0]grid[i][0]dp[i-1][0];}//除了第一行第一列之外for(inti1;im;i){for(intj1;jn;j){dp[i][j]Math.min(dp[i-1][j]grid[i][j],dp[i][j-1]grid[i][j]);}}returndp[m-1][n-1];}}牛客网 二维动态规划 完整题单按类型分类·由易到难按刷题优先级排序优先包含你刚练的矩阵正方形/子结构DP再覆盖经典二维网格DP、二维背包等高频题型无重复、全为牛客原题。一、矩阵正方形 / 子矩形 DP和你当前知识点强关联核心以格子为右下角/左上角依赖左上/左/上状态统计正方形/矩形NC10707 最大正方形思路dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])1求最大边长NC14660 统计全为 1 的正方形子矩阵思路同最大正方形DP累加所有dp[i][j]得到总正方形数NC11039 矩阵中的最大正方形思路字符矩阵0/1版正方形DP边界处理状态转移模板题NC12323 最大黑正方形思路找边框全1的最大正方形预处理行列连续1数组二维DP拓展二、网格路径 DP二维DP入门必刷核心从上到下、从左到右遍历dp[i][j]依赖上方/左方格子NC65 不同路径思路dp[i][j] dp[i-1][j] dp[i][j-1]统计网格路径数NC66 不同路径II思路带障碍物的路径DP障碍物处dp[i][j]0NC59 最小路径和Done思路dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j]求最短路径和NC10575 矩阵最短路径Done思路网格带权值最短路径标准二维DP入门NC17661 地下城游戏思路逆向二维DP从终点倒推起点难度中等三、二维背包 DP经典二维约束DP核心两个约束条件重量体积二维状态dp[i][j]NC127 背包问题V思路二维费用背包约束重量数量经典模板NC145 01背包扩展思路双重限制的01背包二维DP状态定义NC20254 采药II思路时间容量双约束背包二维DP实战四、区间二维 DP 其他经典题型NC83 矩阵最长递增路径思路记忆化搜索二维DP矩阵方向遍历DPNC116 矩阵的最小路径和II思路可走斜向的网格DP拓展状态转移NC13449 硬币找零II思路组合类二维DP统计凑金额的方案数NC12617 最长公共子序列思路字符串二维DPdp[i][j]依赖左/上/左上经典模板刷题建议先刷第一类正方形DP和你刚学的LeetCode1277/221完全通用直接巩固再刷第二类网格路径掌握二维DP最基础的遍历与状态依赖最后刷背包/区间DP拓展二维DP的不同应用场景