动态规划技巧点

动规五部曲（来自b站卡哥）：1、确定DP数组中i、j…的含义。2、确定DP推导式。3、DP数组初始化。4、DP数组遍历顺序。5、DP数组打印校验。

• 父问题、子问题有些许区别：LeetCode343.整数拆分
  今天在哔哩哔哩上刷到了一个非常有意思的leetcode整数拆分的题，博主利用动态规划。我暂时没有想到动态规划来求解，因此先尝试一下记忆性递归，没想到击败100%用户，暂时不清楚leetcode屏蔽逻辑。该题并不是很难，但有一个递归技巧点，因此进行记录。

class Solution {
    public int integerBreak(int n) {
        return integerBreakBy(n, new int[n], true);
    }
    public int integerBreakBy(int i, int[] data, boolean flag){
        if(i <= 1){
            return 1;
        }
        int max = -1;
        int a = flag ? i - 1 : i;
        for(int j = 1; j <= a; j++){
            int i_j = 0;
            if(data[i - j] == 0)
                data[i - j] = integerBreakBy(i - j, data, false);
            int cur_data = j * data[i - j];
            max = max < cur_data ? cur_data : max;  
        }
        return max;
    }
}

由于该题解要求拆出的数字个数要大于1，但是在子递归中，不用进行拆分就也是可以的，因此，引入了一个flag参数，当第一次进行拆分的时候，只要拆分出两个，子问题没有这条限制，所以引入了一个flag。

• dp数组中记录的不一定是整体最优，可能是是包含当前值的最优值，全局最优就可以利用一个变量来记录各个局部最优 300.最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max_value = 0;
        for(int i = 0; i < nums.length; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                // dp[i] = Math.max(dp[i], nums[i] > nums[j] ? dp[j] + 1 : 1);
            }
            if(dp[i] > max_value)
                max_value = dp[i];
        }
        return max_value;
    }
}

以上问题中，dp数组并非记录的是全局最优，而是必须包含当前数字的局部最优。全局最优利用max_value来进行记录。一维dp中，很多需要子遍历的（即第二层遍历j）。