力扣动态规划-2【算法学习day.96】

2025/1/23 2:30:22 来源：https://blog.csdn.net/2301_79232523/article/details/145202692 浏览: 次关键词：力扣动态规划-2【算法学习day.96】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.组合总和IV

题目链接:377. 组合总和 Ⅳ - 力扣（LeetCode）

题面:

记忆化搜索+递归:

class Solution {int[] nums;int[] flag;public int combinationSum4(int[] nums, int target) {this.nums = nums;flag = new int[target+1];Arrays.fill(flag,-1);return recursion(target);}public int recursion(int i){if(i==0)return 1;if(flag[i]!=-1)return flag[i];int sum  = 0;for(int a:nums){if(a<=i){sum+=recursion(i-a);}}return flag[i] = sum;}
}

递推:

class Solution {public int combinationSum4(int[] nums, int target) {int[] flag = new int[target+1];flag[0] = 1;for(int i = 1;i<=target;i++){for(int a:nums){if(a<=i){flag[i]+=flag[i-a];}}}return flag[target];}
}

2.统计构造好字符串的方案数

题目链接:2466. 统计构造好字符串的方案数 - 力扣（LeetCode）

题面:

代码:

class Solution {public int countGoodStrings(int low, int high, int zero, int one) {int[] flag = new int[high+1];flag[0] = 1;int mod = (int)1e9+7;for(int i = 1;i<=high;i++){if(i>=zero){flag[i]=(flag[i-zero]+flag[i])%mod;}if(i>=one){flag[i]=(flag[i-one]+flag[i])%mod;}}int  ans = 0;for(int i = low;i<=high;i++){ans = ans+ flag[i];ans%=mod;}return ans;}
}