寻找前后元素之间的关系 怎么推导得到i+1
寻找前后元素之间的关系 怎么推导得到i+1 可能要借鉴前面几个元素的比如dp[i-1] dp[i-2]
198. House Robber
since we only care about two variables no need to keep all the information in the array
这个题其实是可以类比之前的paint house的。因为对于每一个House都有两个选择 rob还是不rob 而这个
选择是有传递性的 我们先假设第一个房子rob或者不rob 然后之后的房子都建立在这个前提之下进行运算
这里并没有用数组保留数据 因为只用一个变量刚刚够了
public class Solution {
public int rob(int[] nums) {
if(nums == null || nums.length == 0)return 0;
int include = 0;
int exclude = 0;
int len = nums.length;
for(int i = 0;i < len;i++){
int pre = include, e = exclude;
include = e + nums[i];
exclude = Math.max(e, pre);
}
return Math.max(include,exclude);
}
}
213. House Robber II
首尾相连 首部和尾部rob其中一个 覆盖所有情况 只需要调用两次House Robber I的函数 就可以 改一下函数的传入参数 把数组的index传入
public class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 1)return nums[0];
//to rob the first element or not
return Math.max(robPart(nums,0,n-2),robPart(nums,1,n-1));
}
//maximum when rob from [low,high] of array nums
public int robPart(int[] num,int lo,int hi){
int include = 0, exclude = 0;
for (int j = lo; j <= hi; j++) {
int i = include, e = exclude;
include = e + num[j];
exclude = Math.max(e, i);
}
return Math.max(include, exclude);
}
}
337. House Robber III
直接DFS解决 Tree的问题 左右子树考虑 没有Overlap
这道题只有 DP 的一个性质： optimal substructure，即用 subproblem (subtree) 的最优解可以构造出全局最优解。optimal substructure性质在 Tree 类问题中非常常见，因此遇到一个问题的时候，要注意按照其性质属性仔细辨别正确解法。
在 Tree 上做递归的时候返回顺序已然是 bottom-up，相对于每一个节点，并没有重复计算，也没有 overlap subproblems，因此这只是一个正常的递归搜索问题，而不需要依赖 DP 进行优化。
public class Solution {
public int rob(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return root.val;
int leftLvl = 0, rightLvl = 0;
int subleftLvl = 0, subrightLvl = 0;
if(root.left != null){
leftLvl = rob(root.left);
//do not rob root.left but rob its children
subleftLvl = rob(root.left.left) + rob(root.left.right);
}
if(root.right != null){
rightLvl = rob(root.right);
//do not rob root.right but rob its children
subrightLvl = rob(root.right.left) + rob(root.right.right);
}
return Math.max(subleftLvl + subrightLvl + root.val, leftLvl + rightLvl);
}
}
简化版本 进行了优化 一开始是没有想到。。 比较直接的是上面这个版本的
public int rob(TreeNode root) {
int[] result = helper(root);
return Math.max(result[0], result[1]);
}
public int[] helper(TreeNode root){
if(root == null){
int[] result = {0, 0};
return result;
}
int[] result = new int[2];
int[] left = helper(root.left);
int[] right = helper (root.right);
// result[0] is when root is selected, result[1] is when not.
result[0] = root.val + left[1] + right[1];
result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return result;
}
}
256. Paint House
每paint一个房子都有相应的cost 相邻的房子不能paint一样的颜色 但是我们在推测的时候又需要前面的信息
所以这里的DP包含了一定的猜想限制 比如规定DP(i,j)表示第i个房子用了色彩j的情况下的最小值！
/** Since we cannot print the same color adjacent so we do neet the color of the neignboor house
* the dp(i,j) is the minimum cost painting (0...i) house with house i be colored j
* 这种两个变量的方法还是很常见的！
* */
public class Solution {
public int minCost(int[][] costs) {
if(costs == null || costs.length == 0||costs[0].length == 0)return 0;
int n = costs.length;
int[][] dp = new int[n][3];
//base case
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
//decide what's the color for the first house
for(int i = 1;i < n;i++){
dp[i][0] = Math.min(dp[i-1][1] + costs[i][0],dp[i-1][2] + costs[i][0]);
dp[i][1] = Math.min(dp[i-1][0] + costs[i][1],dp[i-1][2] + costs[i][1]);
dp[i][2] = Math.min(dp[i-1][1] + costs[i][2],dp[i-1][0] + costs[i][2]);
}
return Math.min(Math.min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
}
}
拓展：有K个颜色
265. Paint House II
如果继续用上一题的解法也不是不行 就是时间复杂度有些高 。一种想法是从i推测i+1的时候并不需要计算所有情况。。我们只需要
知道使得i取得最小值的时候用的颜色prevColor 然后在选择当前(i + 1)的颜色时如果选择的恰好和prevColor一样那么就用之前的(i)的
第二最小值相加。所以我们要保持每个index对应的第一最小和第二最小 还有最后用了什么颜色
这样最后的时间复杂度就是O(NK)
public class Solution {
public int minCostII(int[][] costs) {
if(costs == null || costs.length == 0) return 0;
int n = costs.length;
int k = costs[0].length;
int prevMin = 0;
int prevMinPtr = -1;
int prevSecMin = 0;
for(int i = 0; i < n; i++){
int curMin = Integer.MAX_VALUE;
int curMinPtr = -1;
int curSecMin = Integer.MAX_VALUE;
for(int j = 0; j < k; j++){
int val = (j == prevMinPtr ? prevSecMin : prevMin) + costs[i][j];
if(val < curMin){
curSecMin = curMin;
curMin = val;
curMinPtr = j;
} else if (val < curSecMin){
curSecMin = val;
}
}
prevMin = curMin;
prevMinPtr = curMinPtr;
prevSecMin = curSecMin;
}
return prevMin;
}
}
276. Paint Fence
更感觉是数学题 。。注意题意理解！！是说没有连着三个相同颜色的 两个是可以的
所以我们在paint位置i的时候 颜色不能和i-1,i-2一样 要么和i-1不一样 要么和i-2不一样
这样递推式出来啦
dp[i] = (i-1) * (dp[i-1] + dp[i-2]);
//不是和i-1不一样就是和i-2不一样？？
public class Solution {
public int numWays(int n, int k) {
int[] dp = new int[n+1];
if(n == 0) return 0;
if(n == 1) return k;
if(n == 2) return k * k;
dp[0] = 0;
dp[1] = k;
dp[2] = k * k;
for(int i = 3;i <= n;i++){
dp[i] = (k - 1)*(dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
}
类似的还有70. Climbing Stairs 求总共ways的 思路一样
62. Unique Paths
因为每个格子只有两种通道可以reach到 所以如果我们把到达上面和左面的格子的路径数目都计算出来 直接叠加两个
就好 二维DP dp[i][j] = dp[i-1][j] + dp[i][j-1] 初始化的时候有两条边哦！而且可以做空间的节省 用一维数组 表示
前一行每一列的路径数 这样更新的时候 已经有了左边的信息和上面的信息
public class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
dp[0] = 1;
for(int i = 0;i < m;i++){
for(int j = 1;j < n;j++){
//left + upper
dp[j] = dp[j] + dp[j-1];
}
}
return dp[n-1];
}
}
63. Unique Paths II
思路还是和straightforward 和62类似 多了一个障碍物 初始化的时候注意一下细节处理 然后就是判断是不是障碍物如果是
当前格子的值清0
/** Pay attention to when do we need to assign the base case if using 1d array
* Since we only keep the information for the first row and that depends on
* whether the given element is an obstacle or not we cannot initiate the base case
* dp[0] outside the loop
* */
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
int[] dp = new int[col];
//if there are only one grid than the start and and are crossing each other
//thus considered to be 1
dp[0] = 1;
for(int i = 0;i < row;i++){
//starts from 0!
for(int j = 0;j < col;j++){
if(obstacleGrid[i][j] == 1){
dp[j] = 0;
}
else if(j > 0){
dp[j] += dp[j - 1];
}
}
}
return dp[col - 1];
}
}
64. Minimum Path Sum
思路和前面两个一样 只不过这次是计算最小值
221. Maximal Square
关键在于怎么规定sub problem 所求的正方形可以以任何(i,j)坐标作为右下角 所以我们可以给这个问题一个Rule 然后
我们计算以(i,j)作为右下角的矩阵时最大的矩阵边长。 然后寻找怎么从已知的推导未知的 拓展正方形 三个方向 横竖对角
所以取左边 右边 还有 左上角的最小值 然后加上本身的贡献（看是否为 1)
public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)return 0;
int m = matrix.length;
int n = matrix[0].length;
//the max length of square take (i,j) as its lower right corner
int[][] dp = new int[m][n];
//base case
int maxArea = 0;
for(int i = 0;i < n;i++){
if(matrix[0][i] == '1'){
dp[0][i] = 1;
maxArea = 1;
}
}
for(int i = 0;i < m;i++){
if(matrix[i][0] == '1'){
dp[i][0] = 1;
maxArea = 1;
}
}
//Iterative
for(int i = 1;i < m;i++){
for(int j = 1;j < n;j++){
if(matrix[i][j] == '1'){
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
}
maxArea = Math.max(dp[i][j] * dp[i][j],maxArea);
}
}
return maxArea;
}
}