网站的制作建站人,东台做网站,wordpress 明星,400电话西安网站制作 彩铃制作动规五部曲#xff08;来自b站卡哥#xff09;#xff1a;1、确定DP数组中i、j…的含义。2、确定DP推导式。3、DP数组初始化。4、DP数组遍历顺序。5、DP数组打印校验。
父问题、子问题有些许区别#xff1a;LeetCode343.整数拆分 今天在哔哩哔哩上刷到了一个非常有意思的l…动规五部曲来自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。
