【知识讲解-题目讲解】算法系列之动态规划入门（下）

目录

前言

Part1. 单词拆分

Part2. 最长递增子序列

Part3. 乘积最大子数组

Part4. 分割等和子集

Part5. 结语

前言

  PS : 上篇文章：【知识讲解-题目讲解】算法系列之动态规划入门（上）-CSDN博客

  在上篇文章中，我们已经讲过关于动态规划的知识，这篇文章将通过更多的题目来深化我们在上篇文章中提到的“反向思考，正向实现”。接下来让我们来看看吧。

let's go!!!!!!!!!

Part1. 单词拆分

  先来看题目：

Leetcode链接：139. 单词拆分 – 力扣（LeetCode）

  这道题目我感觉和在上篇文章中讲到的零钱兑换有着比较大的相似性，都是基于前面的状态来判断后面的状态，我们来看图：

  我们要得到n处的dp值，于是我们遍历从0到n,当dp[m]处的值为1时，我们就判断m到n处的字符是否为题目中给定的字符，如果是那就dp[n]=1,退出循环。不是就继续遍历，直到循环结束，dp[n]=0。

  基本的逻辑已经理顺了，我们来看代码实现：

bool istrue(char* s, char** wordDict, int wordDictSize,int i,int j)//判断j~i的字符是否为题目中给定的字符数组中的一个
{
int goal=i-j;
int a=0;
int b=0;
int yes=0;
for(b=0;b<wordDictSize;b++)
{
for(a=0;a<goal;a++)
{
if(strlen(wordDict[b])!=goal)
break;
if(wordDict[b][a]==s[a+j])
{
yes++;
}
else
{
break;
}
if(yes==strlen(wordDict[b]))
{
break;
}
}
if(yes==strlen(wordDict[b]))
{
return true;
}
yes=0;
}
return false;
}
bool wordBreak(char* s, char** wordDict, int wordDictSize) {
int num=strlen(s);
bool* dp=(bool*)malloc(sizeof(bool)*(num+1));//存储前面的状态
dp[0]=true;//0处的要设置为true(1) 为当题目中给定的单词第一次出现的情况
int i=0;
int j=0;
//循环
for(i=0;i<=num;i++)
{
for(j=0;j<i;j++)
{
if(dp[j]&&istrue(s,wordDict,wordDictSize,i,j))//dp[i]=dp[j]&&string(j~i)
{
dp[i]=true;
break;
}
else
{
dp[i]=false;
}
}
}
return dp[num];//返回最后的结果
}

 依旧是 “反向思考，正向实现”。我们来看下一题：

Part2. 最长递增子序列

  先来看题目：

Leetcode链接：300. 最长递增子序列 – 力扣（LeetCode）

  我们来看这道题的图解：

    我们来看代码：

int give_dp(int i,int* dp,int* nums){
int max=0;
for(int j=0;j<i;j++)//遍历寻找最大的dp[m] 返回最值
if(nums[i]>nums[j])
if(dp[j]>max)
max=dp[j];
return max+1;
}
int lengthOfLIS(int* nums, int numsSize) {
int* dp=(int*)malloc(sizeof(int)*(numsSize+1));
nums=(int*)realloc(nums,sizeof(int)*(numsSize+1));
nums[numsSize]=INT_MAXint;
dp[0]=1;//只有一个数字就自成一派就是长度为一的递增序列
for(int i=1;i<=numsSize;i++)
dp[i]=give_dp(i,dp,nums);
return dp[numsSize]-1;
}

  我们来看下一题：

Part3. 乘积最大子数组

  先来看题目：

Leetcode链接：152. 乘积最大子数组 – 力扣（LeetCode）

  这题相较之前会复杂一点，不过本质还是相同的，我们来看图解：

  我们来看代码：

#define max(a,b,c) (a>b)?((a>c)?a:c):((b>c)?b:c)//返回最大值
#define min(a,b,c) (a<b)?((a<c)?a:c):((b<c)?b:c)//返回最小值
int maxProduct(int* nums, int numsSize) {
if(numsSize==1)
{
return nums[0];
}
int* dp=(int*)malloc(sizeof(int)*(numsSize+1));
int* dp_min=(int*)malloc(sizeof(int)*(numsSize+1));
dp[0]=nums[0];
dp_min[0]=nums[0];
int max_num=0;
for(int i=1;i<numsSize;i++)
{
dp[i]=max(dp[i-1]*nums[i],dp_min[i-1]*nums[i],nums[i]);//公式
dp_min[i]=min(dp[i-1]*nums[i],dp_min[i-1]*nums[i],nums[i]);
}
for(int i=0;i<numsSize;i++)//找到最大的dp值返回（也可以在上面的循环就搞一个变量来接收）
{
if(dp[i]>max_num)
{
max_num=dp[i];
}
}
return max_num;
}

  虽然要维护两个dp，但是还是贯彻了我们上面的思想，我们来看下一题：

Part4. 分割等和子集

  先来看题目：

Leetcode链接：416. 分割等和子集 – 力扣（LeetCode）

  我们先来明确一下这道题的思路：我们要分割等和子集本质上其实就是把整个数组元素的值全部加在一起除以二，然后看数组中是否有元素加在一起可以恰好等于这个数。

  总结一下就是：对于一个数组中的全部元素，是否有其中的某些元素和（不能重复使用数组中的元素）恰好等于一个目标数值。

  那我们怎么完成这个呢？我们来看图解：

  我们来看代码：

bool canPartition(int* nums, int numsSize) {
int i=0;
int mid_num=0;
int q=0;
for(i=0;i<numsSize;i++)
{
mid_num+=nums[i];//计算数组和
}
if(mid_num%2==1)//要是为奇数就直接return false
{
return false;
}
mid_num/=2;
bool* dp=(bool*)malloc(sizeof(bool)*(mid_num+1));
for(i=0;i<=mid_num;i++)
{
dp[i]=false;//初始化为false
}
dp[0]=true;
for(i=0;i<numsSize;i++)
{
for(q=mid_num;q>=0;q–)//也可以从mid_num往前遍历 剪枝优化性能
{
if(q>=nums[i])
{
if(dp[q-nums[i]]==true)
{
dp[q]=true;
}
}
}
}
return dp[mid_num];//返回中间值的状态
}

这题虽然没有明确的公式，但想一想转化一下问题，也是同上面一样的。

Part5. 结语

  结合上一篇对动态规划的介绍，一共讲了八道题目作为动态规划的入门。相信大家对这个以前看上去非常神秘、高冷的算法有了新的认识。关键还是在于“反向思考，正向实现。”

  希望这篇博客可以给大家带来帮助。

最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！

 最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~