当前位置：首页 > article >正文

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

article 2025/1/20 3:38:27

前言

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

习题

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;
    }
}