Dungeon Game

Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

Notes:

  • The knight’s health has no upper bound.
  • Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
            return 0;
        }
        int row = dungeon.length;
        int col = dungeon[0].length;
        //dp[i][j]: the minimum hp knight need to have at dungeon[i][j]
        int[][] dp = new int[row][col];
    
        //init bottom-right cell
        dp[row - 1][col - 1] = Math.max(1 - dungeon[row - 1][col - 1], 1);
    
        //init rightmost rooms
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] =  Math.max(dp[i + 1][col - 1] - dungeon[i][col - 1], 1);
        }
        //init bottom rooms
        for (int j = col - 2; j >= 0; j--) {
            dp[row - 1][j] = Math.max(dp[row - 1][j + 1] - dungeon[row - 1][j], 1);
        }
        //dp
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                dp[i][j] = Math.max(Math.min(dp[i][j + 1] - dungeon[i][j], dp[i + 1][j] - dungeon[i][j]), 1);
            }
        }
    
        return dp[0][0];
    }
FacebookTwitterGoogle+Share

Paint House I & II

Paint House I

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

//dp[i][j]:minimum cost to paint first i houses with house i to be j color
//dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][j]
//given the color of house i
//find the min total cost to paint first i-1 houses
//0:red, 1:green, 2:blue
//time: O(nk) k: # of colors, n: # of houses
public int minCost(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    int row = costs.length;
    int col = costs[0].length;
    int[][] dp = new int[row][col];
    //for house 0, dp[0][j] = costs[0][j]
    for (int j = 0; j < col; j++) {
        dp[0][j] = costs[0][j];
    }
    for (int i = 1; i < row; i++) {
        for (int j = 0; j < col; j++) {
            int min = Integer.MAX_VALUE;
            //given the color of house i
            //find the min total cost to paint first i-1 houses
            for (int k = 0; k < col; k++) {
                if (k == j) {
                    continue;
                }
                min = Math.min(min, dp[i - 1][k]);
            }
            dp[i][j] = min + costs[i][j];
        }
    }
    int minCost = Integer.MAX_VALUE;
    //return min in last row
    for (int j = 0; j < col; j++) {
        minCost = Math.min(minCost, dp[row - 1][j]);
    }
    return minCost;
}

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

public int minCostII(int[][] costs) {
    if (costs == null || costs.length == 0 || costs[0].length == 0) {
        return 0;
    }
    if (costs[0].length == 1) {
        return costs[0][0];
    }
    int n = costs.length;
    int k = costs[0].length;
    //dp 2d array.
    //minCost[i][j]: minimum cost to paint ith house with color j.
    int[][] minCost = new int[n][k];
    //minColor==i: for the current house, use ith color has smallest total value from house 0 ~ i
    int minColor = -1;

    //init first row(1st house)
    int minValue = Integer.MAX_VALUE;
    int secondMinValue = Integer.MAX_VALUE;
    for (int j = 0; j < k; j++) {
        minCost[0][j] = costs[0][j];
        if (minCost[0][j] < minValue) {
            //Important here!
            //if there is a new min, then we need to compare the old min with the secondMinValue
            secondMinValue = Math.min(secondMinValue, minValue);
            minValue = minCost[0][j];
            minColor = j;
        } else if (minCost[0][j] < secondMinValue) {
            secondMinValue = minCost[0][j];
        }
    }
    int preMinValue, preSecondMinValue, preMinColor;
    for (int i = 1; i < n; i++) {
        preMinColor = minColor;
        preMinValue = minValue;
        preSecondMinValue = secondMinValue;
        minColor = -1;
        minValue = Integer.MAX_VALUE;
        secondMinValue = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            //if minCost[i-1][j] is not the smallest
            if (j != preMinColor) {
                minCost[i][j] = preMinValue + costs[i][j];
            }
            //if minCost[i-1][j] is the smallest
            //then we can only use the second smallest one
            else {
                minCost[i][j] = preSecondMinValue + costs[i][j];
            }
            if (minCost[i][j] < minValue) {
                //Important here!
                //if there is a new min, then we need to compare the old min with the secondMinValue
                secondMinValue = Math.min(secondMinValue, minValue);
                minValue = minCost[i][j];
                minColor = j;
            } else if (minCost[i][j] < secondMinValue) {
                secondMinValue = minCost[i][j];
            }
        }
    }
    return minValue;
}

Longest Increasing Continuous subsequence I & II

Longest Increasing Continuous subsequence I 

Give you an integer array (index from 0 to n-1, where n is the size of this array),find the longest increasing continuous subsequence in this array. (The definition of the longest increasing continuous subsequence here can be from right to left or from left to right)

Example

For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.

For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.

Note

O(n) time and O(1) extra space.

Solution:

Longest Increasing Continuous subsequence II

Give you an integer matrix (with row size n, column size m),find the longest increasing continuous subsequence in this matrix. (The definition of the longest increasing continuous subsequence here can start at any row or column and go up/down/right/left any direction).

Example

Given a matrix:

<code>[
  [1 ,2 ,3 ,4 ,5],
  [16,17,24,23,6],
  [15,18,25,22,7],
  [14,19,20,21,8],
  [13,12,11,10,9]
]
</code>

return 25

Challenge

O(nm) time and memory.

Solution:

Longest Increasing Subsequence

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Example

For [5, 4, 1, 2, 3], the LIS  is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

Challenge

Time complexity O(n^2) or O(nlogn)

Clarification

What’s the definition of longest increasing subsequence?

* The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

* https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Solution: DP O(n^2)

lis[i]表示结尾为nums[i]的子序列的最长长度。

所以lis[i] =for all the j<i && nums[j]<=nums[i] max(lis[j])+1

其实还有可以优化为lis[i] = lis[j] +1 where nums[j] 是比nums[i]小的数里最大的一个

public int longestIncreasingSubsequence(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    //lis[i] means the lis of nums[0-i] which i is the last element selected in the lis
    int[] lis = new int[nums.length];
    int maxLis = 0;
    for (int i = 0; i < nums.length; i++) {
        lis[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] >= nums[j]) {
                lis[i] = Math.max(lis[j] + 1, lis[i]);
            }
        }
        maxLis = Math.max(maxLis, lis[i]);
    }
    return maxLis;
}

Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Note

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution: O(n) Time 先参考 Best Time to Buy and Sell Stock I 的做法

这次的不同点在与要做两次交易,所以我们要找一个分界点,分别算左右两边的一次交易利润和的最大值。所以我们可以做Best Time to Buy and Sell Stock I两次

第一次是从左到右扫[0-i]区间,也就是先确定buyDay,然后根据每个prices[i]来确定sellDay。

第二次是从右到左扫[i-end]区间,也就是先确定sellDay,然后根据每个prices[i]来确定buyDay。

所以这两个循环时间都是O(n)

最后我们要用一个循环来设分界点,然后取

max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])

注意这个max不是最终答案,假设只有两天[1,2] 这种情况算下来是0,因为分界点两边都是1天不足以完成交易,而且有可能的情况是第一天买入,最后一天买进,这种情况按两次交易算也无法取到最大值,所以最后结果还要考虑到只做一次交易的情况,因为没有规定必须做两次交易

Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);

这一部分的时间复杂度也是O(n)

所以整体的时间复杂度就是O(n)

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int length = prices.length;
    int[] maxProfitEndedAt = new int[length];
    int[] maxProfitStartedFrom = new int[length];

    //get the max profit from 0 to i with one transaction
    maxProfitEndedAt[0] = 0;
    int buyDay = 0;
    for (int i = 1; i < length; i++) {
        maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
        if (prices[i] < prices[buyDay]) {
            buyDay = i;
        }
    }
    //get the max profit form i to length-1 with one transaction
    maxProfitStartedFrom[length - 1] = 0;
    int sellDay = length - 1;
    for (int i = length - 2; i >= 0; i--) {
        maxProfitStartedFrom[i] = Math.max(maxProfitStartedFrom[i + 1], prices[sellDay] - prices[i]);
        if (prices[i] > prices[sellDay]) {
            sellDay = i;
        }
    }
    //to have two transactions
    //pick a pivot day i, to get the max(maxProfitEndedAt[i]+maxProfitStartedFrom[i+1])
    int maxWithTwoTransaction = 0;
    for (int i = 0; i < length - 2; i++) {
        maxWithTwoTransaction = Math.max(maxWithTwoTransaction,
                                         maxProfitEndedAt[i] + maxProfitStartedFrom[i + 1]);
    }
    return Math.max(maxWithTwoTransaction, maxProfitEndedAt[length - 1]);
}

 

Maximal Square

Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

Example

For example, given the following matrix:

<code>1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
</code>

Return 4.

Solution: DP side[i][j] 表示以(i,j)这个点为右下角可以组成的最大square的边长

由下图可知,大正方形由三个小正方形和(i,j)这个点这个点决定

maximum square草图

side[i][j] = min(side[i-1][j-1], side[i][j-1], side[i-1][j]) +1 //when matrix[i][j]==1

= 0 //when matrix[i][j] = 0

public int maxSquare(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    //side[i][j] = the length of the max square which (i,j) is the at right bottom corner.
    int[][] side = new int[matrix.length][matrix[0].length];
    int max = 0;
    for (int i = 0; i < matrix.length; i++) {
        side[i][0] = matrix[i][0];
        max = Math.max(max, side[i][0]);
    }
    for (int j = 0; j < matrix[0].length; j++) {
        side[0][j] = matrix[0][j];
        max = Math.max(max, side[0][j]);
    }

    for (int i = 1; i < matrix.length; i++) {
        for (int j = 1; j < matrix[i].length; j++) {
            if (matrix[i][j] == 0) {
                side[i][j] = 0;
            } else {
                side[i][j] = Math.min(side[i - 1][j], Math.min(side[i][j - 1], side[i - 1][j - 1])) + 1;
                max = Math.max(max, side[i][j]);
            }
        }
    }
    return max * max;
}

House Robber

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected andit will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example

Given [3, 8, 4], return 8.

Challenge

O(n) time and O(1) memory.

Solution: max[i]表示从0-i个房子里,要抢房子i的最大值

max[i] = Math.max(max[i – 2] + A[i], max[i – 1]);

public long houseRobber(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }
    if (A.length == 1) {
        return A[0];
    }
    if (A.length == 2) {
        return Math.max(A[0], A[1]);
    }

    //max[i] = for [0-i], the max value if rob house i
    long[] max = new long[A.length];
    max[0] = A[0];
    max[1] = A[1];
    for (int i = 2; i < A.length; i++) {
        max[i] = Math.max(max[i - 2] + A[i], max[i - 1]);
    }
    return Math.max(max[A.length - 1], max[A.length - 2]);
}

K Sum

Lintcode Online Judge

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

 Example

Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

Solution: DP

state:  f[i][j][t]前i个数取j个数出来能否和为t

function: f[i][j][t] = f[i – 1][j – 1][t – a[i]] //取Ai的情况

+ f[i – 1][j][t]//不取Ai的情况

init: f[x][0][0] = 1

O(n*k*t) time O(n*k*t) space

public int kSum(int A[], int k, int target) {
    if (A == null) {
        return 0;
    }
    //kSum[i][j][t]:find j integers from first i integers in the array
    //how many solutions there are to sum up to t
    int[][][] kSum = new int[A.length + 1][k + 1][target + 1];
    for (int i = 0; i <= A.length; i++) {
        kSum[i][0][0] = 1; //select nothing which is also a solution
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= k; j++) {
            for (int t = 1; t <= target; t++) {
                kSum[i][j][t] = kSum[i - 1][j][t];
                if (t >= A[i - 1]) {
                    kSum[i][j][t] += kSum[i - 1][j - 1][t - A[i - 1]];
                }
            }
        }
    }
    return kSum[A.length][k][target];
}

Minimum Adjustment Cost

Online Judge

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|

Example

Given [1,4,2,3] and target = 1, one of the solutions is [2,3,2,3], the adjustment cost is 2 and it’s minimal.

Return 2.

Note

You can assume each number in the array is a positive integer and not greater than 100.

Solution: DP

state: f[i][v] 前i个数,第i个数调整为v,满足相邻两数<=target,所需要的最小代价

function: f[i][v] = min(f[i-1][v’] + |A[i]-v|, |v-v’| <= target)

Time Complexity: O(m*n*t) m: array size n:最大可能的数 t:required range

Space Complexity: O(m*n)

 

public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
    if (A == null || A.size() <= 1) {
        return 0;
    }
    int maxInt = 100;//assume each number in the array is a positive integer and not greater than 100
    int[][] minCost = new int[A.size() + 1][maxInt + 1];
    for (int i = 0; i <= maxInt; i++) {
        minCost[0][i] = 0;
    }
    for (int i = 1; i <= A.size(); i++) {
        for (int j = 0; j <= maxInt; j++) {
            int costAiToJ = Math.abs(A.get(i - 1) - j);
            int min = Integer.MAX_VALUE;
            //|k-j|<=target
            //max(0, j-target) <= k <= min(target+j, maxInt)
            for (int k = Math.max(0, j - target); k <= Math.min(target + j, maxInt); k++) {
                if (minCost[i - 1][k] + costAiToJ < min) {
                    min = minCost[i - 1][k] + costAiToJ;
                }
            }
            minCost[i][j] = min;
        }
    }
    int finalMinCost = minCost[A.size()][0];
    for (int i = 0; i <= maxInt; i++) {
        if (minCost[A.size()][i] < finalMinCost) {
            finalMinCost = minCost[A.size()][i];
        }
    }
    return finalMinCost;
}

Backpack I&II

BackPack I

– different sizes same price, ask maximum solution with fixed bag size

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

 Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

Note

You can not divide any item into small pieces.

Challenge

O(n x m) time and O(m) memory.

O(n x m) memory is also acceptable if you do not know how to optimize memory.

 

Solution 1: DP – O(nm) time and O(nm) memory

state: f[i][j] = “前i”个数,取出一些组成和为<=j的最大值

function: f[i][j] = f[i-1][j – a[i]] + a[i] //取a[i]的情况

o f[i-1][j] //不取a[i]的情况

两种情况取max

public int backPack(int m, int[] A) {
    if (m <= 0 || A == null || A.length == 0) {
        return 0;
    }
    int[][] backPack = new int[A.length + 1][m + 1];
    for (int i = 0; i <= A.length; i++) {
        backPack[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        backPack[0][j] = 0;
    }
    int max = 0;
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            //doesn't contain A[i]
            backPack[i][j] = backPack[i - 1][j];
            //contains A[i]
            if (j >= A[i - 1]) {
                backPack[i][j] = Math.max(backPack[i][j], backPack[i - 1][j - A[i - 1]] + A[i - 1]);
            }
            if (backPack[i][j] > max) {
                max = backPack[i][j];
            }
        }
    }
    return max;
}

Solution 2. O(mn) time O(n) space, 利用行数取模优化空间 rolling array

public int backPack(int m, int[] A) {
    if (m <= 0 || A == null || A.length == 0) {
        return 0;
    }
    int[][] backPack = new int[2][m + 1];
    for (int i = 0; i < 2; i++) {
        backPack[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        backPack[0][j] = 0;
    }
    int max = 0;
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            //doesn't contain A[i]
            backPack[i % 2][j] = backPack[(i - 1) % 2][j];
            //contains A[i]
            if (j >= A[i - 1]) {
                backPack[i % 2][j] = Math.max(backPack[i % 2][j], backPack[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
            }
            if (backPack[i % 2][j] > max) {
                max = backPack[i % 2][j];
            }
        }
    }
    return max;
}

Solution 3: dp

f[i][j] = 前i个item能不能正好组成j

f[i][j] = f[i-1][j-a[i]] //取a[i]

f[i-1][j] //不取a[i]

两者取或

return max j which f[i][j] == true

public int backPack(int m, int[] A) {
    if (m <= 0 || A == null || A.length == 0) {
        return 0;
    }
    boolean[][] backPack = new boolean[A.length + 1][m + 1];
    backPack[0][0] = true;
    for (int i = 1; i <= A.length; i++) {
        backPack[i][0] = true;
    }
    for (int j = 1; j <= m; j++) {
        backPack[0][j] = false;
    }
    int max = 0;
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            backPack[i][j] = backPack[i - 1][j];
            if (j >= A[i - 1]) {
                backPack[i][j] |= backPack[i - 1][j - A[i - 1]];
            }
            if (backPack[i][j]) {
                max = j;
            }
        }
    }
    return max;
}

BackPack II

– different size and price, ask for maximum value with fixed bag size

Solution 1. O(m*n) time, O(m*n) space

f[i][j]:maximum value with first i items in A with a m sized bag

f[i][j] = f[i-1][j – a[i]] + v[i] //取a[i]的情况

= f[i-1][j] //不取a[i]的情况

两者取max, return f[n][m]

public int backPackII(int m, int[] A, int V[]) {
    if (A == null || V == null || m <= 0) {
        return 0;
    }
    int[][] maxValue = new int[A.length + 1][m + 1];
    for (int i = 0; i <= A.length; i++) {
        maxValue[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        maxValue[0][j] = 0;
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            maxValue[i][j] = maxValue[i - 1][j];
            if (j >= A[i - 1]) {
                maxValue[i][j] = Math.max(maxValue[i][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
            }
        }
    }
    return maxValue[A.length][m];
}

Solution 2: O(m*n) time, O(m) space

利用rolling array 进行优化

public int backPackII(int m, int[] A, int V[]) {
    if (A == null || V == null || m <= 0) {
        return 0;
    }
    int[][] maxValue = new int[2][m + 1];
    for (int i = 0; i < 2; i++) {
        maxValue[i][0] = 0;
    }
    for (int j = 0; j <= m; j++) {
        maxValue[0][j] = 0;
    }
    for (int i = 1; i <= A.length; i++) {
        for (int j = 1; j <= m; j++) {
            maxValue[i % 2][j] = maxValue[(i - 1) % 2][j];
            if (j >= A[i - 1]) {
                maxValue[i % 2][j] = Math.max(maxValue[i % 2][j], maxValue[(i - 1) % 2][j - A[i - 1]] + V[i - 1]);
            }
        }
    }
    return maxValue[A.length % 2][m];
}