Leetcode 418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won't exceed 100.
5. Length of each word is greater than 0 and won't exceed 10.
6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Code (Java):

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String str = "";
        
        for (String word : sentence) {
            str += word + " ";
        }
        
        int len = str.length();
        
        int start = 0;
        for (int i = 0; i < rows; i++) {
            start += cols;
            
            if (str.charAt(start % len) == ' ') {
                start++;
                continue;
            }
            
            while ((start % len - 1 >= 0) && str.charAt(start % len - 1) != ' ') {
                start--;
            }
        }
        
        return start / len;
    }
}

Leetcode 410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000
• 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Analysis:
A sequence DP problem. 
Define dp[n + 1][m + 1], where dp[i][k] means for the first i elements, divide into number of k subarrays, dp[i][k] is the minimum largeset sum among them. 

Code (Java):

class Solution {
    public int splitArray(int[] nums, int m) {
        int[] preSum = new int[nums.length + 1];
        
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        
        int[][] dp = new int[nums.length + 1][m + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        dp[0][0] = 0;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = 1; k <= m; k++) {
                    dp[i][k] = Math.min(dp[i][k], Math.max(dp[j][k - 1], preSum[i] - preSum[j]));
                }
            }
        }
        
        return dp[nums.length][m];
    }
}

Leetcode 403. Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 231.
• The first stone's position is always 0.

Example 1:

[0,1,3,5,6,8,12,17]

There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.

Return true. The frog can jump to the last stone by jumping 
1 unit to the 2nd stone, then 2 units to the 3rd stone, then 
2 units to the 4th stone, then 3 units to the 6th stone, 
4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

[0,1,2,3,4,8,9,11]

Return false. There is no way to jump to the last stone as 
the gap between the 5th and 6th stone is too large.

Analysis:
The problem is a classic sequence DP problem. The only trick is we need to define the dp function in a special way: 
dp[i] defines all the possible steps jumps to stone i. So each element of the dp[i] is a list, which stores all the steps from previous stone j. 

So for all previous stone[j], we check if we can reach from stone j to stone i. If yes, we store the steps between stone i and stone j. 

So why not just store the maximal distance between stone j and i. That is, if we can reach stone i in 10 steps, we must reach in 1 - 9 steps? That's wrong. It's because for each jump, we can only move dp[j] - 1, to dp[j] + 1 steps. 

Code (Java):

class Solution {
    public boolean canCross(int[] stones) {
        List<Integer>[] dp = (List<Integer>[]) new ArrayList[stones.length];
        for (int i = 0; i < stones.length; i++) {
            dp[i] = new ArrayList<>();
        }
        dp[0].add(0);

        for (int i = 1; i < stones.length; i++) {
            for (int j = 0; j < i; j++) {
                for (Integer pos : dp[j]) {
                    if (stones[i] >= stones[j] + pos - 1 && 
                        stones[i] <= stones[j] + pos + 1) {
                        dp[i].add(stones[i] - stones[j]);
                        break;
                    }
                }
            }
        }
        
        return !dp[stones.length - 1].isEmpty();
    }
}

Leetcode 377. Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Analysis:
A classic DP problem. Define dp[k + 1], where dp[i] means for the target i, how many ways do we have. So the transist function would be for each target i, we iterate all the nums, and sum up its ways.

Code (Java):

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        for (int k = 1; k <= target; k++) {
            for (int i = 0; i < nums.length; i++) {
                if (k - nums[i] >= 0) {    
                    dp[k] += dp[k - nums[i]];
                }
            }
        }
        
        return dp[target];
    }
}

最初思路：
1.刚开始拿到这道题时，高兴！这不就是 K Sum 的简单版吗？只不过成员可以重复使用。要知道，重复使用成员是可以把DP降一维的！所以果断列出了一维DP (DP[target + 1]，存DP[num] 的组合数)；
2.然后循环的时候，还是老样子，先循环 nums 中的数，再循环 1 ~ target。但是这样写，结果错了！为什么呢？假设这个 nums 数组是排好序的 (我们也可以先排个序)，那么如果这样子循环的话，我们可以看到，我们得到的所有组合中，数全都是从小到大的！比如 nums = [1,2,3,4]，target = 4，那么我们最后求出的组合为 —— {1111, 112, 22, 13, 4}，是不是漏了很多？没错，乱序组合都没有包括在内！

改进思路：
1.改进思路的1同上面的1，略；
2.然后循环的时候，先循环 1～target，再循环 nums 中的数，反过来了！为什么呢？因为这样可以保证当 target = t 的时候，其包含的组合可以以任何一个 nums 中的数结尾！
3.假设还是上例，target = 1时，只有 1，DP[1] = 1；target = 2时，循环 [1,2,3,4]，得到 {11, 2}，DP[2] = 2；然后target = 3时，得到 DP[3] = 1->DP[2] + 2->DP[1] + 3->DP[0] = 4，which 分别是 {111, 21, 12, 3}，我们可以看出，此时包括了所有的组合了，很好！以此类推。。。

Leetcode 363. Max Sum of Rectangle No Larger Than K

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2 
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
             and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

Analysis:

The naive solution would be for each sub-matrix of the matrix, we calculate the sum. We compare with k and get a largest one. Since we can do a presum of the matrix before, so getting the sum of the sub-matrix is O(1) operation. The total time complexity of the solution would be O(m * n * m * n).

A better solution:

Think about the 1D problem: If given a array of nums and target k, how can we get the max sum of the subarray of which its sum is no greater than k? 

The solution is do a presum of the array first, and for each number sum[i], our goal is to find out a sum[j], where sum[i] - sum[j] <= k, In other words,

sum[j] >= sum[i] - k.

Since our goal is to find out the sum cloest to k, here sum[j] should be the smallest number in sum and it's greater or equal to sum[i] - k.

We can use a treeset to store the previous sum[i]. Treeset provides a convenient function called ceiling(val) which returns the smallest number greater or equal to val in the treeSet. So our target is to find out the ceiling of (sum[i] - k).

Overall, the time complexity of the 1D array is O(n * logn).

Then let's go back to the 2-D matrix problem. We can choose any two of the columns, c1 and c2. And do a presum between c1 and c2. Then the 2D problem can be reduced to 1D. 

The overall time complexity is O(n^2 * m * logm). If n >> m, we can do a row-order presum first, find out two rows r1 and r2, do a presum between r1 and r2.

Code (Java):

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int[][] preSum = new int[m][n + 1];
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i][j - 1] + matrix[i][j - 1];
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for (int c1 = 1; c1 <= n; c1++) {
            for (int c2 = c1; c2 <= n; c2++) {
                int[] preSumRow = new int[m];
                for (int row = 0; row < m; row++) {
                    preSumRow[row] = preSum[row][c2] - preSum[row][c1 - 1];
                }
                
                ans = Math.max(ans, getMaxSubarrayHelper(preSumRow, k));
            }
        }
        
        return ans;
    }
    
    private int getMaxSubarrayHelper(int[] nums, int target) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        int ans = Integer.MIN_VALUE;
        int[] preSum = new int[nums.length + 1];
        
        for (int i = 1; i <= nums.length; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        
        treeSet.add(0);
        for (int i = 1; i <= nums.length; i++) {
            Integer num = preSum[i] - target;
            Integer ceiling = treeSet.ceiling(num);
            
            if (ceiling != null) {
                ans = Math.max(ans, preSum[i] - ceiling);
            }
            
            treeSet.add(preSum[i]);
        }
        
        return ans;
    }
}

Leetcode 764. Largest Plus Sign

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000

Example 1:

Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.

Example 2:

Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.

Example 3:

Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.

Note:

1. N will be an integer in the range [1, 500].
2. mines will have length at most 5000.
3. mines[i] will be length 2 and consist of integers in the range [0, N-1].
4. (Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)

Code (Java):

class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {
        Set<Integer> set = new HashSet<>();
        
        for (int[] pair : mines) {
            set.add(pair[0] * N + pair[1]);
        }
        
        int[][] dp = new int[N][N];
        
        int ans = 0;
        
        for (int i = 0; i < N; i++) {
            int count = 0;
            
            // left
            //
            for (int j = 0; j < N; j++) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = count;
            }
            
            // right
            //
            count = 0;
            for (int j = N - 1; j >= 0; j--) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = Math.min(dp[i][j], count);
            }
        }
        
        for (int j = 0; j < N; j++) {
            int count = 0;
            
            // up
            //
            for (int i = 0; i < N; i++) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = Math.min(dp[i][j], count);
            }
            
            count = 0;
            // down
            //
            for (int i = N - 1; i >= 0; i--) {
                count = set.contains(i * N + j) ? 0 : count + 1;
                dp[i][j] = Math.min(dp[i][j], count);
                ans = Math.max(ans,dp[i][j]);
            }
        }
        
        return ans;
    }
}

Leetcode 750. Number Of Corner Rectangles

Given a grid where each entry is only 0 or 1, find the number of corner rectangles.

A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.

Example 1:

Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].

Example 2:

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.

Note:

1. The number of rows and columns of grid will each be in the range [1, 200].
2. Each grid[i][j] will be either 0 or 1.
3. The number of 1s in the grid will be at most 6000.

Solution 1:
One straight-forward solution is: we can iterate any two rows, say r1 and r2, and for every column, we check if grid[r1][c] == grid[r2][c]. IF yes, we increate the count by 1. Then the number of rentangles formed by these two rows are count * (count - 1) / 2.

The time complexity of the solution is O(m^2 * n). 

If the number of rows is significantly greater than number of columns, we can iterate the columns and check the rows for each of the two columns. Then the time complexity is O(n^2 * m).

Solution 2:
Solution 2 is similar to solution 1. The main difference is we use a hash map to save the positions of the two rows.

Code (Java):

class Solution {
    public int countCornerRectangles(int[][] grid) {
        if (grid == null || grid.length < 2 || grid[0] == null || grid[0].length < 2) {
            return 0;
        }
        
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        
        int m = grid.length;
        int n = grid[0].length;
        
        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r1][c] == 1 && grid[r2][c] == 1) {
                        int pos = r1* n + r2;
                        if (map.containsKey(pos)) {
                            int val = map.get(pos);
                            ans += val;
                            map.put(pos, val + 1);
                        } else {
                            map.put(pos, 1);
                        }
                    }
                }
            }
        }
        
        return ans;
    }
}

Leetcode 740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.

Each element nums[i] is an integer in the range [1, 10000].

Analysis:
There are several tricks in the problem.
 -- Since each element nums[i] is within the range of [1, 10000], we can use the bucket sort to sort the nums.
 -- For deleting each nums[i], we can delete all same numbers together. So when we do the bucket sort, we can sum up all the repeated numbers in the same bucket. 
 -- Then the problem is a classic backpack problem. 

Define take[10001] and skip[10001], where take[i] means for number i, we delete the number i, the max number of points. skip[i] means we don't delete it.

Then the transit function should be:
take[i] = skip[i - 1] +  values[i]
skip[i] = Math.max(take[i - 1], skip[i - 1]);


Code (Java):

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] dp = new int[100001];
        
        // step 1: bucket sort
        //
        for (int num : nums) {
            dp[num] += num;
        }
        
        int prevTake = 0;
        int prevSkip = 0;
        
        for (int i = 1; i <= 10000; i++) {
            int currTake = prevSkip + dp[i];
            int currSkip = Math.max(prevSkip, prevTake);
            
            prevTake = currTake;
            prevSkip = currSkip;
        }
        
        return Math.max(prevTake, prevSkip);
    }
}

Leetcode 718. Maximum Length of Repeated Subarray

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

Code (Java):

class Solution {
    public int findLength(int[] A, int[] B) {
        int[][] dp = new int[A.length + 1][B.length + 1];
        
        int maxLen = 0;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        
        return maxLen;
    }
}

Leetcode 712. Minimum ASCII Delete Sum for Two Strings

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.

All elements of each string will have an ASCII value in [97, 122]




Analysis:
Two-sequence DP problem. 

Code (Java):

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        dp[0][0] = 0;
        
        for (int i = 1; i <= s2.length(); i++) {
            dp[0][i] = dp[0][i - 1] + s2.charAt(i - 1);
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), 
                                        dp[i][j - 1] + s2.charAt(j - 1));
                }
            }
        }
        
        return dp[s1.length()][s2.length()];
    }
}

Leetcode 688. Knight Probability in Chessboard

On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).

A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.

Example:

Input: 3, 2, 0, 0
Output: 0.0625
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

Note:

• N will be between 1 and 25.
• K will be between 0 and 100.
• The knight always initially starts on the board.

Analysis:

This is a DP problem. We use dp[K + 1][N][N], where dp[k][i][j] represnts after k steps, how many ways we can reach to the (i, j). So the initial state would be dp[0][i][j] = 1. Final state would be dp[K][r][c].

Code (Java):

class Solution {
    int[][] dirs = {{-2, -1}, {-1, -2}, {-2, 1}, {-1, 2}, {2, -1}, {1, -2}, {1, 2}, {2, 1}};
    public double knightProbability(int N, int K, int r, int c) {
        double[][][] dp = new double[K + 1][N][N];
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[0][i][j] = 1;
            }
        }
        
        for (int step = 1; step <= K; step++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || x >= N || y < 0 || y >= N) {
                            continue;
                        }

                        dp[step][i][j] += dp[step - 1][x][y];
                    }
                }
            }
        }

        return dp[K][r][c] / Math.pow(8, K);
    }
}

Another DP solution:
Another way of thinking this problem is, dp[k][i][j] means in the step k, the number of ways from (r, c) to (i, j). So the initial state would be dp[0][r][c] = 1;

The final state is to sum up all the ways on the board.

Code (Java):

class Solution {
    int[][] dirs = {{-2, -1}, {-1, -2}, {-2, 1}, {-1, 2}, {2, -1}, {1, -2}, {1, 2}, {2, 1}};
    public double knightProbability(int N, int K, int r, int c) {
        double[][][] dp = new double[K + 1][N][N];
        
        dp[0][r][c] = 1;
        
        for (int step = 1; step <= K; step++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (x < 0 || x >= N || y < 0 || y >= N) {
                            continue;
                        }

                        dp[step][i][j] += dp[step - 1][x][y];
                    }
                }
            }
        }

        double sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sum += dp[K][i][j];
            }
        }
        
        return sum / Math.pow(8, K);
    }
}

Leetcode 673. Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2:

Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

Code (Java):

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] lenDP = new int[nums.length];
        int[] countDP = new int[nums.length];
        int maxLen = 1;
        
        for (int i = 0; i < nums.length; i++) {
            lenDP[i] = 1;
            countDP[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (lenDP[i] < lenDP[j] + 1) {
                        lenDP[i] = lenDP[j] + 1;
                        countDP[i] = countDP[j];
                        maxLen = Math.max(maxLen, lenDP[i]);
                    } else if (lenDP[i] == lenDP[j] + 1) {
                        countDP[i] += countDP[j];
                    }
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < lenDP.length; i++) {
            if (lenDP[i] == maxLen) {
                count += countDP[i];
            }
        }
        
        return count;
    }
}

Leetcode 651. 4 Keys Keyboard

Imagine you have a special keyboard with the following keys:

Key 1: (A): Print one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:

Input: N = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation: 
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

Code (Java):

class Solution {
    public int maxA(int N) {
        int[] dp = new int[N + 1];
        dp[1] = 1;
        
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j < i - 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * (i - j - 1));
            }
            
            dp[i] = Math.max(dp[i], dp[i - 1] + 1);
        }
        
        return dp[N];
    }
}

Leetcode 650. 2 Keys Keyboard

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

1. The n will be in the range [1, 1000].

Code (Java):

class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        
        for (int i = 2; i <= n; i++) {
            if (i % 2 == 0) {
                dp[i] = dp[i / 2] + 2;
            } else {
                for (int j = i / 2; j > 0; j--) {
                    if (i % j == 0) {
                        dp[i] = dp[j] + i/j;
                        break;
                    }
                }
            }
        }
        
        return dp[n];
    }
}