动态规划算法练习题

45.?跳跃游戏 II

中等

2K

相关企业

给定一个长度为?n?的?0 索引整数数组?nums。初始位置为?nums[0]。

每个元素?nums[i]?表示从索引?i?向前跳转的最大长度。换句话说，如果你在?nums[i]?处，你可以跳转到任意?nums[i + j]?处:

• 0 <= j <= nums[i]?
• i + j < n

返回到达?nums[n - 1]?的最小跳跃次数。生成的测试用例可以到达?nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
?    从下标为 0 跳到下标为 1 的位置，跳?1步，然后跳?3步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000
• 题目保证可以到达?nums[n-1]

int jump(int* nums, int numsSize){
   int *dp=(int *)malloc(sizeof(int)*numsSize);
   dp[0]=0;
   for(int i = 1 ; i < numsSize ; i++ )
    {
        dp[i] =  numsSize + 1;
    }
   for(int i =1; i< numsSize; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(j + nums[j] >= i)
            {
                dp[i] = fmin(dp[i],dp[j]+1);
            }
        }
    }
   return dp[numsSize-1];

}

97.?交错字符串

相关企业

给定三个字符串?s1、s2、s3，请你帮忙验证?s3?是否是由?s1?和?s2?交错?组成的。

两个字符串?s?和?t?交错?的定义与过程如下，其中每个字符串都会被分割成若干?非空?子字符串：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• 交错?是?s1 + t1 + s2 + t2 + s3 + t3 + ...?或者?t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b?意味着字符串?a?和?b?连接。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：

输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1、s2、和?s3?都由小写英文字母组成

bool isInterleave(char * s1, char * s2, char * s3){
    int len1=strlen(s1),len2=strlen(s2),len3=strlen(s3),dp[105][105]={0};
    if(len3!=(len1+len2)){
        return false;
    }
    dp[0][0]=1;
    for(int i=0;i<=len1;i++){
        for(int j=0;j<=len2;j++){
            int p=i+j-1;
            if(i>0){
                if(dp[i-1][j]==1&&s3[p]==s1[i-1])
                    dp[i][j]=1;
            }
            if(j>0){
                 if(dp[i][j-1]==1&&s3[p]==s2[j-1])
                    dp[i][j]=1;
            }
        }
    }
    return dp[len1][len2];
}

131.?分割回文串

中等

1.4K

相关企业

给你一个字符串?s，请你将?s?分割成一些子串，使每个子串都是?回文串?。返回?s?所有可能的分割方案。

回文串?是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s?仅由小写英文字母组

    int dp[20][20]={0};
   void dfs(char* s, int len, int begin, char*** ans, int* returnSize, int* returnColumnSizes, char** temps, int* tempsSize) {
      if(begin==len){
             char** tmp = malloc(sizeof(char*) * (*tempsSize));
          for (int j = 0; j < (*tempsSize); j++) {
              int tempsColSize = strlen(temps[j]);
              tmp[j] = malloc(sizeof(char) * (tempsColSize + 1));
              strcpy(tmp[j], temps[j]);
          }
          ans[*returnSize] = tmp;
          returnColumnSizes[(*returnSize)++] = *tempsSize;
          return;
       }
      for (int j = begin; j < len; ++j) {
          if (dp[begin][j]==1) {
              char* temp = malloc(sizeof(char) * (j - begin + 2));
                   for (int k = begin; k <= j; k++) {
                        temp[k - begin] = s[k];
                    }
              temp[j - begin + 1] = '\0';
                   temps[(*tempsSize)++]=temp;
              dfs(s, len, j + 1, ans, returnSize, returnColumnSizes, temps, tempsSize);
              --*(tempsSize);
          }
      }
  }
  
  char*** partition(char* s, int* returnSize, int** returnColumnSizes) {
       int i,j,len=strlen(s);
        int retMaxLen = len * (1 << len);
       for(i=0;i<20;i++){
           for(j=0;j<20;j++){
               dp[i][j]=0;
           }
       }
       char*** ans = malloc(sizeof(char**) * retMaxLen);
      *returnSize = 0;
      *returnColumnSizes = malloc(sizeof(int) * retMaxLen);
       for(i=len-1;i>=0;i--){
           for(j=i;j<len;j++){
               if(s[i]==s[j]){
                   if(i==j)
                      dp[i][j]=1;
                   if(j-i==1){
                       dp[i][j]=1;
                   }
                   if(j-i>1){
                       if(dp[i+1][j-1]==1){
                           dp[i][j]=1;
                       }
                   }
               }
           }
       }
        char* temps[len];
       int tempsSize=0;
      dfs(s, len, 0, ans, returnSize, *returnColumnSizes, temps, &tempsSize);
      return ans;
  }

139.?单词拆分

中等

1.9K

相关企业

给你一个字符串?s?和一个字符串列表?wordDict?作为字典。请你判断是否可以利用字典中出现的单词拼接出?s?。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
?    注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s?和?wordDict[i]?仅有小写英文字母组成
• wordDict?中的所有字符串?互不相同

bool wordBreak(char * s, char ** wordDict, int wordDictSize){
   int len=strlen(s),falg=0;
   int dp[301]={0};
   dp[0]=1;
   for(int i=0;i<len;i++){
       for(int j=0;j<wordDictSize;j++){
          int n=strlen(wordDict[j]);
          if(n>(len-i)){
              continue;
          }
           falg=1;
           for(int k=0;k<n;k++){
              if(s[i+k]!=wordDict[j][k]){
                  falg=0;
                }
            }
            if(falg==1&&dp[i]==1){
                dp[i+n]=1;
            }
       }
       
   }
   if(dp[len]==1)
      return true;
   return false;
}

221.?最大正方形

中等

1.4K

相关企业

在一个由?'0'?和?'1'?组成的二维矩阵内，找到只包含?'1'?的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

正在上传…重新上传取消转存失败重新上传取消

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j]?为?'0'?或?'1'

暴力超时：

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    int max=0;
    int m=matrixSize,n=matrixColSize[0];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(matrix[i][j]=='1'){
                printf(" %d %d ",i,j);
                for(int b=1;i+b<=m&&j+b<=n;b++){
                    printf(" b=%d\n",b);
                    int falg=1;
                       for(int k=i;k<b+i;k++){
                           for(int l=j;l<j+b;l++){
                                if(matrix[k][l]!='1'){
                                     falg=0;
                                     break;
                                }
                            }
                       }
                       if(falg==1){
                            if(max<b)
                            {
                                max=b;
                            }
                       }
                       if(falg==0){
                           break;
                       }
                }
                
            }
        }
    }
    return max*max;
}

动态规划：

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize){
    int max=0,dp[301][301]={0};
    int m=matrixSize,n=matrixColSize[0];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(matrix[i][j]=='1'){   
               dp[i+1][j+1]=fmin(fmin(dp[i][j],dp[i][j+1]),fmin(dp[i][j],dp[i+1][j]))+1;
            }
            if(dp[i+1][j+1]>max){
                max=dp[i+1][j+1];
            }
        }
    }
    return max*max;
}

279.?完全平方数

中等

1.6K

相关企业

给你一个整数?n?，返回?和为?n?的完全平方数的最少数量?。

完全平方数?是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9?和?16?都是完全平方数，而?3?和?11?不是。

示例?1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 104

int numSquares(int n) 
{
    int dp[n +1];   //定义dp的大小
    dp[0] = 0;      //定义dp的初始状态
    int min; 
    for(int i = 1 ; i <= n ; i++)
    {
        min = INT_MAX;
        for(int j = 1 ; j*j <= i;j++)
        {
            min = fmin(min, dp[i - j * j]);
        }
        dp[i] = min + 1;
    }
    return dp[n];
}

300.?最长递增子序列

中等

3K

相关企业

给你一个整数数组?nums?，找到其中最长严格递增子序列的长度。

子序列?是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]?是数组?[0,3,1,6,2,2,7]?的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

进阶：

• 你能将算法的时间复杂度降低到?O(n log(n))?吗?

int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize],max=0;
    for(int i=0;i<numsSize;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=fmax(dp[i],dp[j]+1);
            }
        }
        if(dp[i]>max){
            max=dp[i];
        }
    }
    return max;
}

376.?摆动序列

中等

857

相关企业

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为?摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如，?[1, 7, 4, 9, 2, 5]?是一个?摆动序列?，因为差值?(6, -3, 5, -7, 3)?是正负交替出现的。

• 相反，[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列?可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组?nums?，返回?nums?中作为?摆动序列?的?最长子序列的长度?。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

int wiggleMaxLength(int* nums, int numsSize) {
    int up[numsSize];
    memset(up,0,sizeof(int)*numsSize);
    up[0]=1;
    int down[numsSize];
    memset(down,0,sizeof(int)*numsSize);
    down[0]=1;
    int max=0;
    for(int i=0;i<numsSize;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                down[i]=fmax(up[j]+1,down[i]);
            }
            if(nums[i]<nums[j]){
                up[i]=fmax(down[j]+1,up[i]);
            }
            
        }
        if(up[i]>max){
            max=up[i];
        }
        if(down[i]>max){
            max=down[i];
        }
    }
    return max;
}