DP Problems

Memonization Search & Dynamic Programming

Word Break III

Triangle

Word Break

Word Break II

Wildcard Matching

Regular Expression Matching

4 key points DP and coordinate DP

### Unique Paths II

Unique Paths

Climbing Stairs

Largest Divisible Subset

• 求一个子集合，集合中的任意两个数相互取余均为0
• 那么我们考虑，较小数对较大数取余一定不为0，那么问题就变成了看较大数能不能整除这个较小数。那么如果数组是无序的，处理起来就比较麻烦，所以我们首先可以先给数组排序，
• 这样我们每次就只要看后面的数字能否整除前面的数字
• 定义一个动态数组dp，其中dp[i]表示到数字nums[i]位置最大的可整除的子集的长度
• 还需要一个一维数组parent，来保存上一个能整除的数字的位置
• 两个整型变量mx和mx_idx分别表示最大子集合的长度和起始数字的位置
• 我们可以从后往前from size() - 1 to 0遍历数组，对于某个数字i再遍历到末尾from i to size() - 1
• 如果nums[j]能整除nums[i], 且dp[i] < dp[j] + 1的话，更新dp[i]和parent[i]
• 如果dp[i]大于mx了，还要更新mx和mx_idx，最后循环结束后，我们来填res数字，根据parent数组来找到每一个数字，

public class Solution {
    /*
     * @param nums: a set of distinct positive integers
     * @return: the largest subset 
     */
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // write your code here
        Arrays.sort(nums);
        int n = nums.length;
        
        int[] dp = new int[n];
        int[] pre = new int[n];
        
        for(int i = 0; i < n; i ++){
            dp[i] = 1;
            pre[i] = -1;
        }
        
        int max = 0;
        int index = -1;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < i; j ++){
                if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }
            if(dp[i] >= max){
                max = dp[i];
                index = i;
            }
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < max; i ++){
            res.add(nums[index]);
            index = pre[index];
        }
        
        return res;
    }
}

Knight Shortest Path

• 每次移动的是sqrt(13)也就是一个方向移动一格，一个方向移动两格

  int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
  int[] dy = {2, -2, 2, -2, 1, -1, 1, -1};
  

• 层级遍历，要for loop queue size

minimum knight moves

• 层级遍历bfs
• x, y range[-300, 300], we can use BFS to find the minimum steps needed to reach target(x, y)
• 只考虑 x >=0 && y >=0 因为棋盘是对称的.
• 所以x = Math.abs(x); y = Math.abs(y)
• We can limit the search dimension within 310 * 310. Any moves that lead to a position that is outside this box will not yield an optimal result.
• 不可以用Set做visited，因为没有重写equals和hashcode
• boolean[][] visited = new boolean[310][310]

Initially, you used a Set of type int[] to track visited positions. This caused TLE because you didn’t overwrite the hashCode and equals methods for int[]. As a result, Set uses the default hashCode and equals method when checking if an element is already in the set. For equals(), The default implementation provided by the JDK is based on memory location — two objects are equal if and only if they are stored in the same memory address.

Knight Probability in Chessboard

• 并不关心骑士的起始位置，而是把棋盘上所有位置上经过K步还留在棋盘上的走法总和都算出来
• 最后直接返回需要的值即可
• 相似题： Out of Boundary Paths

Longest Increasing Subsequence

Russian Doll Envelopes

Merge Two Sorted Interval Lists

Intersection of Two Arrays

Subarray Sum

Merge Sorted Array

Maximum Subarray

Maximum Submatrix

Range Sum Query - Mutable

Sparse Matrix Multiplication

Merge K Sorted Interval Lists

Merge K Sorted Arrays

Median of K Sorted Arrays

Median of two Sorted Arrays

Greedy

Jump Game II

求走到终点indexnums.length - 1的最少步数

• 一共需要四个参数
• index i 记录每一次操作到达的index
• step count记录目前已经走了几步
• currentMax 表示在当前位置最远达到位置，最远可以走到哪一个index，实际上currentMax = nextMax 从nextMax递过来的参数

• nextMax 表示下一个可到达的最远位置，实际上等于nums[i] + i

• 内循环 while，在currentMax即可以走的步子内，去走，更新nextMax，
• if nextMax >= length - 1, return stepcount
• 外循环 while (index <= currentMax)，因为当nums[i] == 0你会发现nextMax不会增加，且永远也走不到下一个，此时应该跳出，返回0

• ← Previous Post
• Next Post →