Leetcode动态规划II
139. 单词拆分
dp[i]代表s的前i个字符是否可以单词拆分。
边界：
空字符串可以拆分，dp[0] = true
转移方程：
对于前i个字符，只要前面某个位置j可以被拆分，且j到i截取的子串存在于单词列表中，那么dp[i] = true。
时间复杂度On2，空间复杂度On。使用把单词列表先转化为哈希表，使判断是否存的时候速度更快。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] == true && set.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
140. 单词拆分 II
使用回溯， 但是超时了，只能调用一下139题的方法进行剪枝。
if (set.contains(sub) && wordBreak2(s.substring(i + 1)))
只有后面的字符串能进行单词拆分时，才符合条件。
原代码：
class Solution {
List<String> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
Set<String> set;
public void dfs(int begin, String s) {
if (begin == s.length()) {
StringBuilder sb = new StringBuilder();
for (String str : temp) {
sb.append(str + " ");
}
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
return;
}
for (int i = begin; i < s.length(); i++) {
String sub = s.substring(begin, i + 1);
if (set.contains(sub)) {
temp.add(sub);
dfs(i + 1, s);
temp.remove(temp.size() - 1);
}
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
set = new HashSet<>(wordDict);
dfs(0, s);
return res;
}
}
优化后：
class Solution {
List<String> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
Set<String> set;
public void dfs(int begin, String s) {
if (begin == s.length()) {
StringBuilder sb = new StringBuilder();
for (String str : temp) {
sb.append(str + " ");
}
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
return;
}
for (int i = begin; i < s.length(); i++) {
String sub = s.substring(begin, i + 1);
if (set.contains(sub) && wordBreak2(s.substring(i + 1))) {
temp.add(sub);
dfs(i + 1, s);
temp.remove(temp.size() - 1);
}
}
}
//第139题的方法
public boolean wordBreak2(String s) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] == true && set.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
public List<String> wordBreak(String s, List<String> wordDict) {
set = new HashSet<>(wordDict);
dfs(0, s);
return res;
}
}
152. 乘积最大子数组
maxDp[i]代表以i为结尾的子数组的乘积最大值。
minDp[i]代表以i为结尾的子数组的乘积最小值。
边界：
maxDp[0] = minDp[0] = nums[0]
转移方程：
maxDp[i]取以下三者较大值： nums[i]本身，maxDp[i - 1] * nums[i] 和 minDp[i - 1] * nums[i]。
minDp[i]取以下三这较小值： nums[i]本身，maxDp[i - 1] * nums[i] 和 minDp[i - 1] * nums[i]。
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = nums[0];
int[] maxDp = new int[nums.length];
int[] minDp = new int[nums.length];
maxDp[0] = minDp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
maxDp[i] = Math.max(nums[i], Math.max(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));
minDp[i] = Math.min(nums[i], Math.min(maxDp[i - 1] * nums[i], minDp[i - 1] * nums[i]));
res = Math.max(res, maxDp[i]);
}
return res;
}
}
174. 地下城游戏
这道题从左上往右下遍历，求解dp数组十分困难，考虑逆向dp。
dp[i][j]代表从第i行第j列出发，到达右下角，初始最低的生命值数。
边界：
最右下角的格子，如果数组大小dungeon[row - 1][col - 1] 小于0，那么所需的最低生命值数就是它的相反数加1。 如果大于等于0，那么所需的最低生命值数是1。
最后一行的某个位置的dp值，可由它右边那个格子的dp值推出。如果dp[i + 1][col - 1] - dungeon[i][col - 1] 大于0，那么就等于这个数。如果小于等于0，只要初始生命值为1就行。
最后一列同理。
转移方程：
对于第i行第j个格子，考虑往下走还是往右走，肯定是往dp值更小的方向走。
那么dp[i][j] 就等于右边和下边的dp较小值减去 dungeon[i][j]，如果这个值小于等于0，初始生命值为1就行，如果大于0，那么就等于这个值。
class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int row = dungeon.length, col = dungeon[0].length;
int[][] dp = new int[row][col];
if (dungeon[row - 1][col - 1] < 0) {
dp[row - 1][col - 1] = -dungeon[row - 1][col - 1] + 1;
} else {
dp[row - 1][col - 1] = 1;
}
for (int i = row - 2; i >= 0; i--) {
dp[i][col - 1] = Math.max(1, dp[i + 1][col - 1] - dungeon[i][col - 1]);
}
for (int j = col - 2; j >= 0; j--) {
dp[row - 1][j] = Math.max(1, dp[row - 1][j + 1] - dungeon[row - 1][j]);
}
for (int i = row - 2; i >= 0; i--) {
for (int j = col - 2; j >= 0; j--) {
dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
}
}
return dp[0][0];
}
}
198. 打家劫舍
dp[i]代表偷前i个房屋的最高金额。
边界：
dp[0] = nums[0]
转移方程
dp[i] = max(dp[i-2] + nums[i] , dp[i-1])
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
}
return dp[nums.length - 1];
}
}
优化：
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
int p = 0, q = nums[0], r = nums[0];
for (int i = 1; i < nums.length; i++) {
r = Math.max(p + nums[i], q);
p = q;
q = r;
}
return r;
}
}
213. 打家劫舍 II
分为两种情况，偷第一家和不偷第一家。
由于不可能第一家和最后一家都不偷，所以可以把环形问题转化成和212题一样的问题。
偷第一家的时候，最后一家不能去偷。
不偷第一家的时候，最后一家可以去偷。
然后取两者较大值即可。
class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];//偷第一家
for (int i = 1; i < nums.length; i++) {
if (i == nums.length - 1) {//最后一家不能偷
dp[i] = dp[i - 1];
}
dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
}
int res = dp[nums.length - 1];
Arrays.fill(dp, 0);
dp[0] = 0;//不偷第一家
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
}
res = Math.max(res, dp[nums.length - 1]);
return res;
}
}
221. 最大正方形
dp[i][j]代表以第i行第j列的格子作为正方形最右下顶点的正方形最大边长。
边界：
第一行和第一列的某个格子如果为0，则dp值为0。如果为1，则dp值为1。
转移方程：
matrix[i][j]如果等于1，则dp[i][j] 与它左边，上边，左上 三个格子有关。等于三者最小值+1。
matrix[i][j]如果等于0，则dp[i][j] = 0
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int row = matrix.length, col = matrix[0].length;
int[][] dp = new int[row][col];
int res = 0;
for (int i = 0; i < row; i++) {
dp[i][0] = matrix[i][0] == '0' ? 0 : 1;
res = Math.max(res, dp[i][0]);
}
for (int j = 1; j < col; j++) {
dp[0][j] = matrix[0][j] == '0' ? 0 : 1;
res = Math.max(res, dp[0][j]);
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][j] == '0') {
dp[i][j] = 0;
} else {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
res = Math.max(res, dp[i][j]);
}
}
return res * res;
}
}
