# 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];
}```
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.

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]的子序列的最长长度。

```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

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 的做法

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

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

```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;
for (int i = 1; i < length; i++) {
maxProfitEndedAt[i] = Math.max(maxProfitEndedAt[i - 1], prices[i] - prices[buyDay]);
}
}
//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的边长

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];
}```

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

## – 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]的情况

```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;
}```

## – 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]的情况

```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

```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];
}```