【Hello Algorithm】暴力递归到动态规划（二）

**特别需要注意的是 我们使用数组之前一定要进行初始化 不然很有可能会遇到一些意想不到的错误 比如说在Linux平台上 new出来的int数组会初始化为0 但是在leetcode网页上默认初始化确不是0 博主因为这个错误找了好久 **

由于缓存法（记忆化搜索）实在是太简单了 所以说从本篇博客开始 我们直接从递归到完整的动态规划 不再经历缓存法

背包问题

递归版本

现在给我们两个数组 一个数组表示货物的重量 一个数组表示货物的价值 它们的下标一一对应切一定大于等于0

现在给定我们一个参数bag 表示我们背包能够承受重量的最大值 现在要求背包能够装的价值的最大值

我们的思考过程如下

我们设置函数的意义是 从第index件货物开始拿 我们能拿进背包的最大价值

首先想base case

• 如果此时背包的大小小于0 则说明背包无法装下任何货物 （背包大小可以为0 因为有可能货物的重量为0）
• 如果index等于数组的长度 则说明没有任何货物了 返回0

之后我们写出的代码如下

int process(vector<int>& w , vector<int>& v , int index , int bag)      
{                                                                       
  if (bag < 0 )                                                         
  {                                                                     
    return 0;                                                           
  }                                                                     
                                                                        
  if (index == static_cast<int>(w.size()))                              
  {                                                                     
    return 0;                                                           
  }                                                                     
                                                                        
  int p1 = process(w , v , index + 1 , bag);                            
  int p2 = v[index] + process(w , v , index + 1 , bag - w[index]);      
    
  return  max(p1 , p2);                                                                                                         
}          
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

但是这里我们的base case其实是有问题的

因为如果我们只有一个货物 即使p2超重了 我们仍然会走p2这条分支 并且会拿走这个超重的货物 这显然是不合适的 所以说我们需要改写下base case和选择代码

修改后的代码如下

int process(vector<int>& w , vector<int>& v , int index , int bag)    
{                 
  if (bag < 0 )    
  {    
    return -1;                                
  }    
                 
  if (index == static_cast<int>(w.size()))    
  {    
    return 0;                                   
  }              
                                                            
  int p1 = process(w , v , index + 1 , bag);    
  int p2 = 0;        
  int next = process(w , v ,index + 1 , bag - w[index]);    
                             
  if (next != -1)    
  {    
    p2 = v[index] + next;    
  }                                                                                                                             
    
  return  max(p1 , p2);    
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

动态规划

我们观察下原函数

process(vector<int>& w , vector<int>& v , int index , int bag)    
1

变化的参数只有index 和 bag 所以说我们只要建立index和bag的二维表就能解决问题

我们首先看每个格子依赖于什么

  int p1 = process(w , v , index + 1 , bag);    
  int p2 = 0;        
  int next = process(w , v ,index + 1 , bag - w[index]);  
1
2
3

观察上面的两个函数 我们就能得到下图

每个格子依赖于它下面的两个格子 （如果存在的话）

所以说我们的动态规划要从最下面开始 从左往右填

  for (int dpindex = w.size() - 1 ; dpindex >= 0  ; dpindex--)
  {
    for(int dpbag = 0; dpbag <= bag ; dpbag++)
    {
      int p1 = dp[dpindex + 1][dpbag];
      int p2 = 0;
      if (dpbag - w[dpindex] >= 0)
      {
        p2 = v[dpindex] + dp[dpindex+1][bag - w[dpindex]];
      }

      dp[dpindex][dpbag] = max(p1 , p2);
    }                                                                                                                           
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这样子我们的动态规划代码就完成了

数字字符串改字母字符串

递归版本

我们规定 1数字代表 ‘a’ 2数字代表 ‘b’ … … 以此类推

现在给你一串数字字符 要求你返回能改成字母字符串的最大解法

函数表示如下

int process(string& str , int index)
1

该函数的意义是 从str的index位置开始 按题目要求有的最大解法

我们首先来想base case

• 如果index此时走到了str.size() 此时就是一个空串 空串也是一种解法 再拼接上前面的字符串 就是一种完整的解法
• 如果index单独走到了数字0的位置 那么此时就没有解法了

之后我们来想普遍情况 当前字符单独转化 ？ 还是当前字符 + 下面一个字符转化 ？

当然如果是当前字符 + 下面一个字符转化的话我们要考虑一些特殊情况

代码表示如下

int process(string& str , int index)
{            
  if (index == static_cast<int> (str.length()))
  {
    return 1;           
  }
             
  if (str[index] == '0')
  {
    return 0; 
  }                 

  // need cur 
  // need cur + 1 ?                                                                                        
  int p1 = process(str , index + 1);                                                                                            
  int p2 = 0;                     
  if (index + 1 < static_cast<int>(str.length()) &&  (str[index] - '0') * 10 + (str[index+1] - '0')  < 27 )
  {
    p2 = process(str , index + 2);
  }

  return p1 + p2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

动态规划

我们发现 递归函数中只依赖于一个参数index

int process(string& str , int index)
1

于是乎我们可以建立一张一维表

再通过递归函数看下依赖关系

 int p1 = process(str , index + 1);                                                                                            
  int p2 = 0;                     
  if (index + 1 < static_cast<int>(str.length()) &&  (str[index] - '0') * 10 + (str[index+1] - '0')  < 27 )
  {
    p2 = process(str , index + 2);
  }
1
2
3
4
5
6

我们能够得到下图

此时index + 2 不一定依赖 我们只需要加上一点判断条件即可

字符串贴纸

现在给定一个字符串str 给定一个字符串类型的数组arr 出现的字符全部是小写的英文字母

arr每一个字符串 代表一张贴纸 每种贴纸有无限多个 你可以把单个字符剪开使用 目的是拼出来str来返回需要至少多少张贴纸 返回一个最小值

例子： str = “babac” arr = {“ba” ， “c” ，“abcd”}

至少需要两张贴纸 “abcd” “abcd”

递归版本

我们这么定义递归函数

int process(vector<string> stickers , string target)
1

这个函数的含义是 告诉我们贴纸的数量 告诉我们目标字符串 要求我们返回一个最小值

首先想base case

如果说target为空串了 此时我们只需要返回0即可

  if (target.size() == 0)    
  {    
    return 0;    
  }    
1
2
3
4

完整递归函数如下

int process(vector<string>& stickers , string target)                                                                           
{    
  if (target.size() == 0)    
  {    
    return 0;    
  }    
    
  int Min = INT32_MAX;    
  for (auto first : stickers)    
  {    
    string rest = strminus(target , first);    
    if (rest.length() != target.length())    
    {    
      Min = min(Min , process(stickers , rest));    
    }    
  }    
    
  Min = Min + (Min == INT32_MAX ? 0 : 1);    
  return Min;    
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们设置一个int类型的值 Min 作为一个系统最大值

之后遍历整个贴纸数组 看看贴纸数组中的字符能不能减少目标target

如果能 我们就继续递归下去 让递归函数给我们一个最大值 如果不能我们就继续遍历下一个贴纸

最后我们看看Min是不是还是系统最大值 如果是就直接返回 如果不是 我们就让Min+1之后返回 （因为此时我们只是得到了去除第一张贴纸之后的最小值 所以说最后要加一）

动态规划

我们首先看原函数 影响它的参数是什么

int process(vector<string>& stickers , string target) 
1

我们发现只有一个target字符串在变化 但是我们对于字符串的变化是很难进行操作的

所以说对于这一题的动态规划我们采用记忆化搜索的方案

多加一个参数 map 每次得到数据之前先把数据填进去即可

代码表示如下

int process(vector<string>& stickers , string target , map<string , int>& dp)    
{    
  if (dp.find(target) != dp.end())     
  {    
    return dp.find(target)->second;    
  }    
    
  if (target.size() == 0)    
  {    
    return 0;    
  }    
    
  int Min = INT32_MAX;    
  for (auto first : stickers)    
  {    
    string rest = strminus(target , first);    
    if (rest.length() != target.length())    
    {    
      Min = min(Min , process(stickers , rest , dp));    
    }    
  }    
    
  Min = Min + (Min == INT32_MAX ? 0 : 1);    
  dp[target] = Min;                                                                                                             
  return Min;    
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26