• 将求某个序列/数组转化

  • 为求以i个数结尾的值，使得通项公式更容易计算
  • 此时最终返回值常为Math.max/min (f[1...n])

• 通项公式有几种构成思路

  1. 跟前几项有关，i = (i-1) + (i-2) + (i-3) etc
  2. 跟前面所有项的和有关 dp[i] = dp[0] + ..+ dp[i-1]
  3. 跟前面所有项的最大/小值有关 dp[i] = min(dp[0], ... , dp[i-1])

Longest Increasing Subsequence

O(n^2)的一般DP解法

• f[i]为以i结尾的数LIS
• 注意这里

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int result = 1;
        int len = nums.length;
        int[] dp = new int[len];

        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {

            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            result = Math.max(result, dp[i]);
        }

        return result;
    }
}

• Follow up
  • 返回具体的LIS：加一个新 array，记录 parent index 一路追踪就可以了,和 Largest Divisible Subset 一样。
  • O(nlogn)

O(nlogn)利用binarySearch优化

• dp保存的不再是以index结尾的长度，而是保存当不断从左向右扫时的获得这个LIS的最小末尾
• 这样dp是sorted的。所以就可以用binarySearch来找到当前num的位置。
  • 如果这个位置存在，并且比要加入的nums[i]大，那么则将当前的dp[pos]更新为nums[i]
  • 如果这个位置不存在（比当前的递增长度大），则直接加入到递增的最后，同时更新当前的递增长度

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ptr = 0;
        for(int i = 1; i < nums.length; i++){
            int pos = binarySearch(dp, 0, ptr, nums[i]);
            if(dp[pos] > nums[i]) dp[pos] = nums[i];
            if(pos > ptr){
                ptr = pos;
                dp[pos] = nums[i];
            }
        }

        return ptr + 1;
    }

    private int binarySearch(int[] dp, int start, int end, int target){
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            if(target > dp[mid]){
                start = mid;
            } else {
                end = mid;
            }
        }

        // This equality sign is important
        // otherwise it would return wrong insert position
        if(dp[start] >= target) return start;
        if(dp[end] < target) return end + 1;

        return end;
    }
}

参考了https://mnmunknown.gitbooks.io/algorithm-notes/content/chapter1.html

[Perfect Squares]

这是另外一种类型，当dp[i]的通项公式很难由i+-1推测出来了以后，需要考虑通项公式中i的表达式是否可以由题目的条件来进行表示， 比如这里关心的是平方数问题，那么当i = x + y^2时，就可以有 dp(x+y^2) = min(dp(x+y^2), dp(x)+1)这样的通项公式。

• 观察到，在枚举的过程中，有一些组合显然不是最优的，比如把12拆成12个1相加。另外，如果我们能够记录已经找到的最小组合，那么稍大一些的数只需要在此基础上添加若干个完全平方数即可。这里面就包含了动态规划的思想
• 另外要注意区别，所给的是含n个元素的数组，还是一组数从1~n，对于从1~n的情况，dp数组应该存n+1个数，返回dp[n]，并且要注意对dp[0]的初始化

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i <= n; i++) {
            for (int j = 1; i + j*j <= n; j++) {
                dp[i + j*j] = Math.min(dp[i + j*j], dp[i] + 1);
            }
        }

        return dp[n];
    }
}

Largest Divisible Subset

• 注意到这里有两次比较，第一次是dp[i]是dp从0到j中的最大值+1，另外一个是要获取最大的LDS，即每一个获得的dp需要再进行比较
• 求某个具体解
  • 多用一个数组来保存具体解中，每个位置的坐标，这里保存的方式比较独特，是一个『离散跳跃』的保存，index[i]=j即第i位，保存的是dp[i]的subset中除了nums[i]这个数以外，所选取的那个dp[j]中的最大的值，j的坐标。而这个j，又是由上一次dp决定了。

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        int len = nums.length;

        //store the index of the largest number in the i-1 subset
        int[] index = new int[len];
        int[] dp = new int[len];
        Arrays.sort(nums);
        Arrays.fill(dp, 1);
        Arrays.fill(index, -1);

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {                    
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        index[i] = j;
                    }       
                }
            }
        }

        int max = 0;
        int maxIndex = 0;
        for (int i = 0; i < len; i++) {
            if (dp[i] > max) {
                max = dp[i];
                maxIndex = i;
            }
        }

        while (maxIndex != -1) {
            result.add(nums[maxIndex]);
            maxIndex = index[maxIndex];
        }

        return result;
    }
}