2025高频面试算法总结篇【递归回溯动态规划】

递归&回溯

131. 分割回文串

回溯思路：

临界条件：
if (start == s.length) => 保存
循环遍历这个字串
for (int i = start;i < s.length();i++)
    if (s[start:i] 是 回文串) => dfs(i+1)

回文串的判断：

1. 可以直接判断。
2. 可以采用动态规划的方式进行记录，dp[i][j]定义为s[i:j]字串是否是回文串，d[i][j] = s[i]==s[j] && d[i+1][j-1]

class Solution {

    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return ans;
        }
        dfs(s, 0, new ArrayList<>());
        return ans;
    }
    
    private void dfs (String s, int start, List<String> res) {
        if (start == s.length()) {
            ans.add(new ArrayList<>(res));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (huiwen(s.substring(start, i+1))) {
                res.add(s.substring(start, i+1));
                dfs(s, i+1, res);
                res.remove(res.size() - 1);
            }
        }
    }

    private boolean huiwen(String substring) {
        int left = 0;
        int right = substring.length() -1;
        while (left < right) {
            if (substring.charAt(left) != substring.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    


}

面试题 08.12. 八皇后

回溯思路：定义一个一维数组即可cols[row] = x,第row行的皇后在第x列。

临界条件：
if (row == N) =》保存
递归&回溯：遍历当前这一行的数据
for (int col = 0; col < N; col++)
    if [row][col] 符合 题意 ：=》下一行dfs(row+1)

[row][col] 符合 题意:

1. 不同行已经确保了，需要判断不同列：cols[0:row] != col
2. 对角线的判断：row - col == i - cols[i]（左对角线冲突）& row + col == i + cols[i]（右对角线冲突）【简单记忆：绝对值：行-遍历的行==列-遍历的列Math.abs(row - i) == Math.abs(col - cols[i])】

class Solution {
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        if (n == 0) return ans;
        dfs(0, n, new int[n]);
        return ans;
    }

    private void dfs(int row,int n, int[] cols) {
        if (row == n) {
            // 保存
            ans.add(board(cols));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (helper(row, col, cols)) {
                cols[row] = col;
                dfs(row+1, n, cols);
                cols[row] = 0;
            }
        }
    }

    private boolean helper(int row,int col,int[] cols) {
        if (row == 0) return true;
        for (int i = 0; i < row; i++) {
            if (cols[i] == col
            || Math.abs(row - i) == Math.abs(col - cols[i])) {
                return false;
            }
        }
        return true;
    }

    private List<String> board (int[] cols) {
        List<String> res = new ArrayList<>();
        char[] s = new char[cols.length];
        for (int i = 0; i < cols.length; i++) {
            Arrays.fill(s, '.');
            s[cols[i]] = 'Q';
            res.add(new String(s));
        }
        return res;
    } 

        
}

动态规划

72编辑距离

定义：dp[i][j]表示word1[0:i]编辑成word2[0:j]所使用的最少操作数 。
公式：初始 i=0 dp[0][j] = j , j=0, dp[i][j] = i， if s[i] == s[j] dp[i][j] = dp[i-1][j-1] else dp[i][j] = 1+ Math.min(插入dp[i][j-1],删除dp[i-1][j], 替换 dp[i-1][j-1])

class Solution {
    // 定义
    // dp[i][j]:  word1[0:i] 转换成 word2[0:j] 所使用的最少操作数
    // 边界
    // d[0][0] = 0
    // d[i][0] = i d[0][j] = j
    // 状态转移
    // dp[i][j] =
    // if w1[i] == w2[j] => dp[i][j] = dp[i-1][j-1]
    // else 删插换 dp[i][j] = 1 + min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

5. 最长回文子串

定义：dp[i][j] 表示 s[i:j]是否是回文串
公式：dp[i][i] = true 单个字符一定是回文串，dp[i][j] = (s[i] == s[j]) && (len == 2 || dp[i + 1][j - 1])

class Solution {
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        int start = 0;
        int maxLen = 1;
        for (int len = 2; len <= s.length(); len++) {
            for (int i = 0; i <= s.length() - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && maxLen < len) {
                    maxLen = len;
                    start = i;
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}

279. 完全平方数

定义：dp[i] 和为 i 的完全平方数的最少数量 。
公式： dp[0]=0 dp[i]=Math.min(dp[i], dp[i-j*j]+1)

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i;j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

300. 最长递增子序列

定义：dp[i] 表示以nums[i]结尾的最长递增子序列的长度。
公式：dp[i]=max(dp[i],dp[j]+1)(其中 j<i 且 nums[j]<nums[i])

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // dp[i] = dp[i-x] + 1
        int[] dp = new int[nums.length + 1];
        Arrays.fill(dp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > dp[nums.length]) {
                dp[nums.length] = dp[i];
            }
        }
        return dp[nums.length];
    }
}

139. 单词拆分

状态定义：dp[i] 表示 s[0:i] 是否可以拆分成 wordDict 里的单词组合。

转移方程： dp[i]=dp[j] 且 s[j:i] 在 wordDictdp[i] = dp[j]

• 遍历 j < i，如果 dp[j] 是 true，且 s[j:i] 是 wordDict 里的单词，则 dp[i] = true。

初始化：

• dp[0] = true，表示空字符串可以被拆分。

import java.util.*;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict); // 用 HashSet 加速查找
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // 空字符串可以拆分

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // 发现可拆分后立即终止，优化性能
                }
            }
        }
        return dp[n];
    }
}