一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ）。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。問總共有多少條不同的路徑？

題解:數組, 動態規劃

• 由一維轉為二維了, 其實規劃式子還是和前面的狀態有關. 比如dp[i][j]表示到達(i,j)的所有路徑, 又(i,j)只會從(i-1,j)&(i,j-1)移動而來, 那么, dp[i][j]=dp[i-1][j]+dp[i][j-1]

• class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i=0;i<m;i++){dp[i][0]=1;}for(int j=0;j<n;j++){dp[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
  }
  

64. 最小路徑和

給定一個包含非負整數的 *m* x *n* 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。說明：每次只能向下或者向右移動一步。

題解:數組, 動態規劃

• 跟前面那題一樣, 其實走一遍圖就知道了. dp[i][j]代表點(i,j)最小路徑和, 那么第0排和第0列的數據是遍歷一遍可以計算出來的: 當前grid值+前一位置的dp值

• 那么其余位置可以計算了, dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j]

• class Solution {public int minPathSum(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 i=1;i<m;i++){dp[i][0] = dp[i-1][0]+grid[i][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++){for(int j=1;j<n;j++){dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}return dp[m-1][n-1];}
  }
  

給你一個字符串 s，找到 s 中最長的 回文 子串。

題解:子串, 遞歸, 動態規劃

• 如果一個字符串為回文串, 那么左右各縮減1的子串也為回文串

• dp[][]存儲的是(i,j)處的串是否為回文串, 如果是, 那么s[i] == s[j] &&dp[i+1][j-1]同時也是回文串

• 怎么根據上面的式子找出動態規劃呢, 我們最后肯定要維護一個最長回文子串大小以及begin處, 這樣返回的才是s.substring(begin,begin+mL)

• dp[i][i]肯定是回文的, 因為只有一個字符, 初始化以下; 計算是否回文, 或許可以用雙指針, 一個指向頭, 一個指向假定len的尾, 那么這個len要從多大開始呢–第二條可以得出: dp[i][j] = s[i]==s[j] && dp[i+1][j-1]

• 我們需要先得出內部子串是否為回文, 那么len要從最小判斷: for(int len = 2;i<=s.length();l++), 然后遍歷s,從s的索引i處到i+len-1處, 看當前子串是否為回文的即可

• class Solution {public String longestPalindrome(String s) {int n = s.length();if(n < 2) return s;int mL=1;int begin = 0;boolean[][] dp = new boolean[n][n];char[] chs = s.toCharArray();for(int l = 2;l<=n;l++){for(int i=0;i<n;i++){int j = i+l-1;if(j >= n) break;if(chs[i] != chs[j]){dp[i][j] = false;}else{if(j-i < 3) dp[i][j] = true;else{dp[i][j] = dp[i+1][j-1];}}if(j-i+1 > mL&dp[i][j]){mL = j-i+1;begin = i;}}}return s.substring(begin,begin+mL);}
  }
  

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。

題解:子串, 動態規劃

• 其實這題我建議記下來, 因為很久不用這題的邏輯總會忘記, 但是代碼又是很簡單的

• class Solution {public int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();int[][] dp = new int[m+1][n+1];char[] chs1 = text1.toCharArray();char[] chs2 = text2.toCharArray();for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(chs1[i-1] == chs2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];}
  }
  

72. 編輯距離

給你兩個單詞 word1 和 word2， 請返回將 word1 轉換成 word2 所使用的最少操作數 。你可以對一個單詞進行如下三種操作：插入一個字符; 刪除一個字符; 替換一個字符

題解:最長公共子序列, 動態規劃

• 本題需要維護的是dp[i][j] , 表示A的前i個字母與B的前j個字母之間的編輯距離

• class Solution {public int minDistance(String word1, String word2) {int n = word1.length();int m = word2.length();if(n*m == 0) return n+m;int[][] dp = new int[n+1][m+1];for(int i=0;i<=n;i++){dp[i][0]=i;}for(int j=0;j<=m;j++){dp[0][j] = j;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){int left = dp[i-1][j]+1;int down = dp[i][j-1]+1;int left_down = dp[i-1][j-1];if(word1.charAt(i-1)!= word2.charAt(j-1)){left_down+=1;}dp[i][j] = Math.min(left,Math.min(down,left_down));}}return dp[n][m];}
  }