核心思想
尝试函数有 1 个可变参数可以完全决定返回值，进而可以改出 1 维动态规划表的实现 同理 尝试函数有 2 个可变参数可以完全决定返回值，那么就可以改出 2 维动态规划的实现
一维、二维、三维甚至多维动态规划问题，大体过程都是： 写出尝试递归 ->记忆化搜索 (从顶到底的动态规划) ->严格位置依赖的动态规划 (从底到顶的动态规划) 空间、时间的更多优化
动态规划表的大小：每个可变参数的可能性数量相乘
动态规划方法的时间复杂度：动态规划表的大小 * 每个格子的枚举代价
二维动态规划依然需要去整理动态规划表的格子之间的依赖关系 找寻依赖关系，往往通过画图来建立空间感，使其更显而易见 然后依然是从简单格子填写到复杂格子的过程，即严格位置依赖的动态规划 (从底到顶)
二维动态规划的压缩空间技巧需要很细心的画图来整理具体题目的依赖关系 最后进行空间压缩的实现
能改成动态规划的递归，统一特征： 决定返回值的可变参数类型往往都比较简单，一般不会比 int 类型更复杂。为什么？
从这个角度，可以解释带路径的递归（可变参数类型复杂），不适合或者说没有必要改成动态规划 题目 2 就是说明这一点的
一定要写出可变参数类型简单（不比 int 类型更复杂），并且可以完全决定返回值的递归， 保证做到这些可变参数可以完全代表之前决策过程对后续过程的影响！再去改动态规划！
不管几维动态规划 经常从递归的定义出发，避免后续进行很多边界讨论 这需要一定的经验来预知
例题
1、最小路径和
题目描述： 给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：
输入：grid = [[1,2,3],[4,5,6]] 输出：12
递归的目的是将问题划分为一个又一个依赖的子问题，且每个子问题的求解过程是一致的
其中首先要找出的是其中的出节点，即什么除了正常返回结果，还有那个状态可以直接从递归过程中跳出来
这里找最小路径和，只允许向右向下看，那么根据题目要求找到从左上角到右下角的路径
那么每次都是从某个节点如 (i, j) 分来 2 条分支，一条代表向下，一条代表向右
这写分支总体将会呈二叉树状，最后要么到达目标节点，要么出边界
最终你能到达目标节点的分支上一节要么是向下而来，要么是向右而来，递归中间的子项就出来了
由于是找最小，那么加上一个比较就可以
我们是求到达目标节点的最小路径，注定最开始调递归的时候状态节点只能是目标节点
那么就是二叉树一步步往上一层看
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code01_MinimumPathSum
* @description: 最小路径和
* // 给定一个包含非负整数的 m x n 网格 grid
* // 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
* // 说明：每次只能向下或者向右移动一步。
* // 测试链接 : https://leetcode.cn/problems/minimum-path-sum/
* @author: zs宝
* @create: 2025-08-08 10:19
* @Version 1.0
**/
package main.java.class067;
public class Code01_MinimumPathSum {
class Solution {
public int minPathSum(int[][] grid) {
return minPathSum4(grid);
}
/**
暴力递归的方法，会超时
*/
public int minPathSum1(int[][] grid) {
return f1(grid,grid.length-1,grid[0].length-1);
}
//递归的解法
public int f1(int[][] grid,int i,int j){
//当到达00的位置上时，直接返回
if(i==0 && j==0){
return grid[0][0];
}
//由于只能向右或者向下移动
//那么对于在i,j位置的最短路径值则与其左边和上边的值有关
int up=Integer.MAX_VALUE;
int left=Integer.MAX_VALUE;
//求上面的值，不能越界
if(i-1>=0){
up=f1(grid,i-1,j);
}
if(j-1>=0){
left=f1(grid,i,j-1);
}
return grid[i][j]+Math.min(up,left);
}
/**
记忆化搜索:由暴力递归解法优化而来
自顶向下 */
public int minPathSum2(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int[][]dp=new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dp[i][j]=-1;
}
}
return f2(grid,m-1,n-1,dp);
}
public int f2(int[][] grid,int i,int j,int[][]dp){
//当到达00的位置上时，直接返回
if(i==0 && j==0){
return grid[0][0];
}
if(dp[i][j]!=-1){
return dp[i][j];
}
//由于只能向右或者向下移动
//那么对于在i,j位置的最短路径值则与其左边和上边的值有关
int up=Integer.MAX_VALUE;
int left=Integer.MAX_VALUE;
//求上面的值，不能越界
if(i-1>=0){
up=f2(grid,i-1,j,dp);
}
if(j-1>=0){
left=f2(grid,i,j-1,dp);
}
int ans=grid[i][j]+Math.min(up,left);
dp[i][j]=ans;
return ans;
}
/**
严格按照位置依赖的动态规划：由记忆化搜索优化而来
*/
public int minPathSum3(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int[][]dp=new int[m][n];
dp[0][0]=grid[0][0];
//第一行只能由向右走而来
for(int j=1;j<n;j++){
dp[0][j]=dp[0][j-1]+grid[0][j];
}
//第一列只能由向下走而来
for(int i=1;i<m;i++){
dp[i][0]=dp[i-1][0]+grid[i][0];
}
//接下来对中间的dp值进行更新
//由于只能向右或者向下走
//因此除开第一行第一列的dp值都是与上边和左边的数相关
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
/**
严格按照位置依赖的动态规划+空间压缩
*/
public int minPathSum4(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
int[]dp=new int[n];
dp[0]=grid[0][0];
//将第一行的dp计算出来
for(int j=1;j<n;j++){
dp[j]=dp[j-1]+grid[0][j];
}
//依次更新，一行一行往下走
for(int i=1;i<m;i++){
//每次第0列的都只能由上一列向下走
dp[0]=dp[0]+grid[i][0];
for(int j=1;j<n;j++){
//这里依次更新
dp[j]=grid[i][j]+Math.min(dp[j],dp[j-1]);
}
}
return dp[n-1];
}
}
}2、单词搜索
题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和word仅由大小写英文字母组成
对于其中关于回溯的部分，最开始是使用的 visited 的布尔类型的数组表示某个位置已经使用了，不可再使用，但仔细观察这个数据量只有小写字母，完全可以不适用一个数组，只需要将其中的字符修改一个永远不会出现的字符即可，上下左右递归完后，状态回溯复原即可
这道题是无法由递归改为动态规划的，因为其中每轮判定都有一个递归路径状态的更改，这种带路径的递归（可变参数类型复杂），不适合或者说没有必要改成动态规划
char temp=board[i][j];
board[i][j]='0'; 代码
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code02_WordSearch
* @description: 单词搜索（无法改成动态规划）
* // 给定一个 m x n 二维字符网格 board 和一个字符串单词 word
* // 如果 word 存在于网格中，返回 true ；否则，返回 false 。
* // 单词必须按照字母顺序，通过相邻的单元格内的字母构成
* // 其中"相邻"单元格是那些水平相邻或垂直相邻的单元格
* // 同一个单元格内的字母不允许被重复使用
* // 测试链接 : https://leetcode.cn/problems/word-search/
* @author: zs宝
* @create: 2025-08-09 10:06
* @Version 1.0
**/
package main.java.class067;
public class Code02_WordSearch {
class Solution {
public boolean exist(char[][] board, String word) {
int m=board.length;
int n=board[0].length;
char[] words=word.toCharArray();
int number=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(f1(board,words,i,j,number)){
return true;
}
}
}
return false;
}
public boolean f1(char[][] board, char[] words,int i,int j,int number) {
if(number==words.length){
return true;
}
if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=words[number]){
return false;
}
//表示遍历过了i,j位置，后续上下左右的递归操作不让使用这个位置的值
char temp=board[i][j];
board[i][j]='0';
//上下左右移动
number++;
boolean ans=f1(board,words,i+1,j,number) || f1(board,words,i,j+1,number)
|| f1(board,words,i-1,j,number) || f1(board,words,i,j-1,number);
//上下左右完成后，状态还原
board[i][j]=temp;
return ans;
}
}
}3、最长公共子序列
题目描述： 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
提示：
1 <= text1.length, text2.length <= 1000text1和text2仅由小写英文字符组成。
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code03_LongestCommonSubsequence
* @description: 最长公共子序列
* // 给定两个字符串text1和text2
* // 返回这两个字符串的最长 公共子序列 的长度
* // 如果不存在公共子序列，返回0
* // 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列
* // 测试链接 : https://leetcode.cn/problems/longest-common-subsequence/
* @author: zs宝
* @create: 2025-08-09 10:32
* @Version 1.0
**/
package main.java.class067;
public class Code03_LongestCommonSubsequence {
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] str1=text1.toCharArray();
char[] str2=text2.toCharArray();
return longestCommonSubsequence4(str1,str2);
}
/**
暴力递归：不够适合转为动态规划
*/
public static int longestCommonSubsequence0(char[] text1,char[] text2) {
int n=text1.length;
int m=text2.length;
return f0(text1, text2, n - 1, m - 1);
}
// s1[0....i1]与s2[0....i2]最长公共子序列长度
public static int f0(char[] s1, char[] s2, int i1, int i2) {
if (i1 < 0 || i2 < 0) {
return 0;
}
int p1 = f0(s1, s2, i1 - 1, i2 - 1);
int p2 = f0(s1, s2, i1 - 1, i2);
int p3 = f0(s1, s2, i1, i2 - 1);
int p4 = s1[i1] == s2[i2] ? (p1 + 1) : 0;
return Math.max(Math.max(p1, p2), Math.max(p3, p4));
}
/**
暴力递归的方式：优化上面的暴力递归，使逻辑更清楚更适合后续的转为动态规划
*/
public int longestCommonSubsequence1(char[] text1,char[] text2){
int n=text1.length;
int m=text2.length;
return f1(text1,text2,n,m);
}
/**
text1的的i位置往前，text2的j位置往前(其实也就是剩余字符的长度，i/j位置及其往后的都判断过了)，最长公共子序列长度事多少
*/
public int f1(char[] text1,char[] text2,int i,int j){
if(i==0 || j==0){
return 0;
}
int ans;
if(text1[i-1]==text2[j-1]){
ans= f1(text1,text2,i-1,j-1)+1;
}else{
ans=Math.max(f1(text1,text2,i-1,j),f1(text1,text2,i,j-1));
}
return ans;
}
/**
记忆化搜索：由暴力递归优化而来
*/
public int longestCommonSubsequence2(char[] text1,char[] text2){
int n=text1.length;
int m=text2.length;
int[][]dp=new int[n+1][m+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=-1;
}
}
return f2(text1,text2,n,m,dp);
}
/**
text1的的i位置往前，text2的j位置往前(其实也就是剩余字符的长度)，最长公共子序列长度事多少
*/
public int f2(char[] text1,char[] text2,int i,int j,int[][]dp){
if(i==0 || j==0){
return 0;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int ans;
if(text1[i-1]==text2[j-1]){
ans=f2(text1,text2,i-1,j-1,dp)+1;
}else{
ans=Math.max(f2(text1,text2,i-1,j,dp),f2(text1,text2,i,j-1,dp));
}
dp[i][j]=ans;
return ans;
}
/**
严格按照位置的动态规划：由记忆化搜索优化而来
*/
public int longestCommonSubsequence3(char[] text1,char[] text2){
int n=text1.length;
int m=text2.length;
int[][]dp=new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(text1[i-1]==text2[j-1]){
dp[i][j]=1+dp[i-1][j-1];
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
/**
严格按照位置的动态规划+空间压缩
*/
public int longestCommonSubsequence4(char[] text1,char[] text2){
//让s1永远为较长的那个字符数组
char[]s1,s2;
if(text1.length>=text2.length){
s1=text1;
s2=text2;
}else{
s1=text2;
s2=text1;
}
int n=s1.length;
int m=s2.length;
//空间压缩让其为较短字符数组的长度，进一步节省空间
int[]dp=new int[m+1];
for(int i=1;i<=n;i++){
int leftUp=0,backup;
for(int j=1;j<=m;j++){
//记录下一轮位置的左上的数
backup=dp[j];
if(s1[i-1]==s2[j-1]){
dp[j]=1+leftUp;
}else{
//比较左边和上边的值
dp[j]=Math.max(dp[j-1],dp[j]);
}
//注意更新每次的左上位置的数值
leftUp=backup;
}
}
return dp[m];
}
}
}4、最长回文子序列
题目描述： 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code04_LongestPalindromicSubsequence
* @description: 最长回文子序列
* // 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度
* // 测试链接 : https://leetcode.cn/problems/longest-palindromic-subsequence/
* @author: zs宝
* @create: 2025-08-10 14:30
* @Version 1.0
**/
package main.java.class067;
public class Code04_LongestPalindromicSubsequence {
class Solution {
public int longestPalindromeSubseq(String s) {
return longestPalindromeSubseq4(s);
}
/**
暴力递归解法：超时
*/
public int longestPalindromeSubseq1(String s) {
char[]str=s.toCharArray();
int n=s.length();
//定义str在从[i,j]位置中的最长回文子串
return f1(str,0,n-1);
}
//str在从[i,j]位置中的最长回文子串
//i<=j
public int f1(char[]str,int i,int j){
//当i到j只有一个字符时
if(i==j){
return 1;
}
//当i到j只有2个字符时
if(i+1==j){
return str[i]==str[j]?2:1;
}
if(str[i]==str[j]){
//若[i,j]间字符有多个，且i位置与j位置字符相同，则最长回文子串为[i+1,j-1]之间的最长回文子串+2
//+2是因为i,j位置的字符算上有2个长度
return f1(str,i+1,j-1)+2;
}else{
return Math.max(f1(str,i+1,j),f1(str,i,j-1));
}
}
/**
记忆化搜索：由暴力递归优化而来
*/
public int longestPalindromeSubseq2(String s) {
char[]str=s.toCharArray();
int n=s.length();
int[][]dp=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
dp[i][j]=-1;
}
}
//定义str在从[i,j]位置中的最长回文子串
return f2(str,0,n-1,dp);
}
//str在从[i,j]位置中的最长回文子串
//i<=j
public int f2(char[]str,int i,int j,int[][]dp){
//当i到j只有一个字符时
if(i==j){
return 1;
}
//当i到j只有2个字符时
if(i+1==j){
return str[i]==str[j]?2:1;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
int ans;
if(str[i]==str[j]){
//若[i,j]间字符有多个，且i位置与j位置字符相同，则最长回文子串为[i+1,j-1]之间的最长回文子串+2
//+2是因为i,j位置的字符算上有2个长度
ans=f2(str,i+1,j-1,dp)+2;
}else{
ans=Math.max(f2(str,i+1,j,dp),f2(str,i,j-1,dp));
}
dp[i][j]=ans;
return ans;
}
/**
严格按照位置的动态规划：由记忆化搜索优化而来
*/
public int longestPalindromeSubseq3(String s) {
char[]str=s.toCharArray();
int n=s.length();
int[][]dp=new int[n][n];
for(int i=n-1;i>=0;i--){
for(int j=i;j<n;j++){
if(i==j){
dp[i][j]=1;
}else if(i+1==j){
dp[i][j]=str[i]==str[j]?2:1;
}else{
if(str[i]==str[j]){
dp[i][j]=2+dp[i+1][j-1];
}else{
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
}
return dp[0][n-1];
}
/**
严格按照位置的动态规划+空间压缩
*/
public int longestPalindromeSubseq4(String s) {
char[]str=s.toCharArray();
int n=s.length();
int[]dp=new int[n];
int leftdown=0,backdown;
for(int i=n-1;i>=0;i--){
dp[i]=1;
if(i+1<n){
leftdown = dp[i + 1];
dp[i+1]=str[i]==str[i+1]?2:1;
}
for(int j=i+2;j<n;j++){
backdown=dp[j];
if(str[i]==str[j]){
dp[j]=leftdown+2;
}else{
dp[j]=Math.max(dp[j-1],dp[j]);
}
leftdown=backdown;
}
}
return dp[n-1];
}
}
}5、二叉树
题目描述： 小强现在有nn个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为nn且树的高度不超过mm的方案.因为答案很大,所以答案需要模上1e9+7后输出. 树的高度: 定义为所有叶子到根路径上节点个数的最大值.
例如: 当n=3,m=3时,有如下5种方案:
数据范围：1≤n,m≤50 1≤n,m≤50
进阶：时间复杂度O(mn2) O(mn2) ，空间复杂度O(nm) O(nm)
输入描述：
第一行输入两个正整数nn和mm. 1≤m≤n≤501≤m≤n≤50 输出描述：
输出一个答案表示方案数. 示例1 输入： 3 3 输出： 5 示例2
输入：
3 2
输出：
1
示例3
输入：
4 3
输出：
6
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code05_NodenHeightNotLargerThanm
* @description: 节点数为n高度不大于m的二叉树个数
* // 现在有n个节点，计算出有多少个不同结构的二叉树
* // 满足节点个数为n且树的高度不超过m的方案
* // 因为答案很大，所以答案需要模上1000000007后输出
* // 测试链接 : https://www.nowcoder.com/practice/aaefe5896cce4204b276e213e725f3ea
* @author: zs宝
* @create: 2025-08-10 14:42
* @Version 1.0
**/
package main.java.class067;
import java.util.*;
import java.io.* ;
public class Code05_NodenHeightNotLargerThanm {
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int n, m;
public static int MOD = 1000000007;
public static int MAXN = 51;
public static void main(String[] args) throws IOException {
BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(buffer);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int)in.nval;
in.nextToken();
m = (int)in.nval;
out.println(compute4(n, m));
}
out.flush();
out.close();
buffer.close();
}
/**
暴力递归
*/
public static int compute1(int n, int m) {
if (n == 0) {
return 1;
}
if (m == 0) {
return 0;
}
long ans = 0;
//二叉树
// 一共n个节点，头节点已经占用了1个名额
//把左右子树又当成一个二叉树的问题来求解
//现在左右子树节点和只能为n-1，左右子树节点最多为n-1个
// 如果左树占用k个，那么右树就占用n-k-1个
for (int k = 0; k < n; k++) {
ans = (ans + ((long) compute1(k, m - 1) * compute1(n - k - 1,
m - 1)) % MOD) % MOD;
}
return (int)ans;
}
/**
记忆化搜索: 由暴力递归优化而来
*/
public static long[][]dp1 = new long[MAXN][MAXN];
static {
for (int i = 0; i < MAXN; i++) {
for (int j = 0; j < MAXN; j++) {
dp1[i][j] = -1;
}
}
}
public static int compute2(int n, int m) {
if (n == 0) {
return 1;
}
if (m == 0) {
return 0;
}
if (dp1[n][m] != -1) {
return (int)dp1[n][m];
}
long ans = 0;
//二叉树
// 一共n个节点，头节点已经占用了1个名额
//现在左右子树节点和只能为n-1，左右子树节点最多为n-1个
// 如果左树占用k个，那么右树就占用i-k-1个
for (int k = 0; k < n; k++) {
ans = (ans + ((long) compute2(k, m - 1) * compute2(n - k - 1,
m - 1)) % MOD) % MOD;
}
dp1[n][m] = ans;
return (int)ans;
}
// 严格位置依赖的动态规划
public static long[][] dp2 = new long[MAXN][MAXN];
public static int compute3(int n, int m) {
//第0行全部为1,n==0
for (int j = 0; j <= m; j++) {
dp2[0][j] = 1;
}
//第一列全部为0,m==0
for (int i = 1; i <= n; i++) {
dp2[i][0] = 0;
}
//从左到右，从上到下
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp2[i][j] = 0;
for (int k = 0; k < i; k++) {
dp2[i][j] = (dp2[i][j] + (dp2[k][j - 1] * dp2[i - k - 1][j - 1]) % MOD) % MOD;
}
}
}
return (int)dp2[n][m];
}
// 严格位置依赖的动态规划+空间压缩
public static long[] dp3 = new long[MAXN];
public static int compute4(int n, int m) {
//n==0时
dp3[0]=1;
//第0列
for(int i=1;i<=n;i++){
dp3[i]=0;
}
//这里的顺序变为1列1列的从下往上看（画个二维表格很容易看出来）
for(int j=1;j<=m;j++){
for(int i=n;i>=1;i--){
dp3[i]=0;
for(int k=0;k<i;k++){
dp3[i]=(dp3[i] + (dp3[k] * dp3[i - k - 1]) % MOD) % MOD;
}
}
}
return (int)dp3[n];
}
}
}6、矩阵中的最长递增路径
题目描述： 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4 解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]] 输出：4 解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
示例 3：
输入：matrix = [[1]] 输出：1
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
此题如果由记忆化搜索转为严格按照位置的动态规划，并不合适，因为它需要四个方向的值，无论怎样构建这个二维 dp 你都难以构建出让 4 个方向有值而中间刚好空出位置的那种
/**
* @program: ZuoChengxunAlgorithmClass
* @ClassName Code06_LongestIncreasingPath
* @description: 矩阵中的最长递增路径
* // 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度
* // 对于每个单元格，你可以往上，下，左，右四个方向移动
* // 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）
* // 测试链接 : https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/
* @author: zs宝
* @create: 2025-08-10 15:46
* @Version 1.0
**/
package main.java.class067;
public class Code06_LongestIncreasingPath {
class Solution {
public int longestIncreasingPath(int[][] matrix) {
return longestIncreasingPath2(matrix);
}
/**
暴力递归解法
*/
public int longestIncreasingPath1(int[][] matrix) {
int m=matrix.length;
int n=matrix[0].length;
int ans=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
ans=Math.max(ans,f1(matrix,i,j));
}
}
return ans;
}
/**
从矩阵matrix的i,j位置出发所能找到的最长递增路径
*/
public int f1(int[][] matrix,int i,int j){
//越界
if(i<0 || i>matrix.length || j<0 || j>matrix[0].length){
return 0;
}
//后续若可以往上下左右移动，移动的最大递增路径长度是多少
int next=0;
//向下走
if(i+1<matrix.length && matrix[i][j]<matrix[i+1][j]){
next=Math.max(next,f1(matrix,i+1,j));
}
//向左走
if(j-1>=0 && matrix[i][j]<matrix[i][j-1]){
next=Math.max(next,f1(matrix,i,j-1));
}
//向上走
if(i-1>=0 && matrix[i][j]<matrix[i-1][j]){
next=Math.max(next,f1(matrix,i-1,j));
}
if(j+1<matrix[0].length && matrix[i][j]<matrix[i][j+1]){
next=Math.max(next,f1(matrix,i,j+1));
}
//不要忘记next是从上下左右的位置开始的最长递增路径，加上自己本身位置还有个1
return next+1;
}
/**
记忆化搜索：暴力递归优化而来
*/
public int longestIncreasingPath2(int[][] matrix) {
int m=matrix.length;
int n=matrix[0].length;
int[][]dp=new int[m][n];
int ans=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
ans=Math.max(ans,f2(matrix,i,j,dp));
}
}
return ans;
}
/**
从矩阵matrix的i,j位置出发所能找到的最长递增路径
*/
public int f2(int[][] matrix,int i,int j,int[][]dp){
//越界
if(i<0 || i>matrix.length || j<0 || j>matrix[0].length){
return 0;
}
if(dp[i][j]!=0){
return dp[i][j];
}
//后续若可以往上下左右移动，移动的最大递增路径长度是多少
int next=0;
//向下走
if(i+1<matrix.length && matrix[i][j]<matrix[i+1][j]){
next=Math.max(next,f2(matrix,i+1,j,dp));
}
//向左走
if(j-1>=0 && matrix[i][j]<matrix[i][j-1]){
next=Math.max(next,f2(matrix,i,j-1,dp));
}
//向上走
if(i-1>=0 && matrix[i][j]<matrix[i-1][j]){
next=Math.max(next,f2(matrix,i-1,j,dp));
}
if(j+1<matrix[0].length && matrix[i][j]<matrix[i][j+1]){
next=Math.max(next,f2(matrix,i,j+1,dp));
}
dp[i][j]=next+1;
//不要忘记next是从上下左右的位置开始的最长递增路径，加上自己本身位置还有个1
return next+1;
}
}
}