网站建设如何盈利网站推广优化服务
动规五部曲（来自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）。