---

遞歸&回溯

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] + 1int[] 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];}
}

---