hot100之多维动态规划
我是比较爱用自底向上的自底向上方法不会计算多余情况， 也不用memo存储不同路径（062）
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int;
for (int i = 0; i < m;i++){
dp = 1;
}
for (int j = 0; j < n; j++){
dp = 1;
}
for (int i = 1; i < m; i++){
for (int j = 1; j < n; j++){
dp = dp + dp;
}
}
return dp;
}
}
[*]分析
对0行0列初始化，后进行合流
最小路径和（064）
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid.length;
int[][] dp = new int;
dp = grid;
for (int i = 1; i < m; i++){
dp = dp + grid;
}
for (int j = 1; j < n; j++){
dp = dp + grid;
}
for (int i = 1; i < m; i++){
for (int j = 1; j < n; j++){
dp = Math.min(dp, dp) + grid;
}
}
return dp;
}
}
[*]分析
同样是初始化， 再合流
根据dp数组的依赖关系， 可以进行空间优化
最长回文子串（005）
class Solution { public String longestPalindrome(String s) { String res = " "; for (int i = 0; i < s.length(); i++){ String str1 = longestSubPalindrome(i, i, s); String str2 = longestSubPalindrome(i, i+1, s); res = res.length() > str1.length() ? res : str1; res = res.length() > str2.length() ? res : str2; } return res; } private String longestSubPalindrome(int lef, int rig, String s){ while (0
页:
[1]