6.暴力递归转动态规划

2023-05-16

动态规划

1.什么是动态规划？

动态规划就是暴力递归（回溯）的过程中有重复调用的过程，动态规划在算过每次调用后把答案记下来，下次再遇到重复过程直接调用这个行为就叫动态规划。

动态规划就是对有重复调用过程的暴力递归过程的优化。

例子：斐波那契数列f(n) = f(n - 1) + f(n - 2),f(1) = 1, f(2) = 1。求f(5)

$**[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hlf2m40S-1648111812917)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1647525250317.png)]**$

可以看出求F（5）的过程中会有很多的重复调用（红色的为重复调用），这种重复过程会浪费大量的时间。

如果我们重复过程我们之前算过，我们给它记到一个表里去，如果下次再遇到这个重复过程，我们不需要调用，直接从表里拿值就会快得多，这就是动态规划。

2.暴力尝试（回溯）优化成动态规划的步骤

暴力尝试（回溯）优化成动态规划的步骤：

写出暴力尝试版本
转换成记忆化搜索（基础动态规划版本）
根据base case和调用过程画表，转换成动态规划。
优化动态规划。如斜率优化。

例：有排成一行的N个位置，记为1~n，n>=2.开始时，机器人在start位置上（1<=start<=N）.如果机器人来到1位置，那么下一步只能来到2位置；如果机器人来到N位置，下一步只能来到N-1位置；如果机器人来到中间位置，下一步可以来到N-1或N+1位置。规定机器人必须走K步，最终能来到aim位置的方法有多少种。

测试用例：n = 4, cur = 2, aim = 4, k = 4。结果为3

1.写出暴力尝试代码

//n表示有n个位置， cur为当前位置， aim为目标位置， k为剩余步数。
//返回从cur出发，走过k步后，到aim位置的方法数是多少
int ways(int n, int cur, int aim, int k) {
    //base case, 没有步数了。
    if (k == 0) {
        if (cur == aim) { //正好走到aim位置
            return 1;
        } 
        return 0; //没有走到aim位置
    }
    if (cur == 1) { //最左边只能往右走
        return ways(n, cur + 1, aim, k - 1);
    } else if (cur == n) { //最右边只能往左走
        return ways(n, cur - 1, aim, k - 1);
    } else {//中间可以往两边走
        return ways(n, cur - 1, aim, k - 1) + ways(n, cur + 1, aim, k - 1);
    }
}
int main() {
    cout << ways(4, 2, 4, 4);
    return 0;
}
//打印结果为3

2.根据递归函数的可变参数修改成记忆化搜索。

上述ways函数的递归函数中，n和aim是固定参数，每次调用都不会变，而cur和k每次调用过程都会变，因此ways函数的调用结果取决于cur和k的值，我们只要用一个二维表来记录每个调用过程的返回值便能大大提高效率，这种方法叫做记忆缓存法。

//cur的范围：1~n   k的范围：0~k
int ways2(int n, int cur, int aim, int k, vector<vector<int>>& dp) {
    if (dp[cur][k] != -1) { //这个递归过程记录过直接返回结果
        return dp[cur][k];
    }
    //之前没算过
    int ans = 0;
    if (k == 0) {
        ans = cur == aim ? 1 : 0;
        return ans;
    }
    if (cur == 1) {
        ans = ways2(n, cur + 1, aim, k - 1, dp);
    }
    else if (cur == n) {
        ans = ways2(n, cur - 1, aim, k - 1, dp);
    }
    else {
        ans = ways2(n, cur - 1, aim, k - 1, dp) + ways2(n, cur + 1, aim, k - 1, dp);
    }
    dp[cur][k] = ans;
    return ans;
}
int main() {
    //n = 4, k = 2,dp为5 * 3的二维数组表
    vector<vector<int>> dp(5, vector<int>(3, -1));
    cout << ways2(4, 2, 4, 2, dp) << endl;
    cout << dp[2][2];
    return 0;
}
//打印结果为:
1
1

3.画表转换成动态规划

测试用例：n = 5, cur = 4, aim = 6, k = 6。

由于n = 5，cur的变化范围为1~5，k = 6，k的变化范围为0~6，我们可以画出一个6×7的二维表。

看base case：由于cur的变化范围为1~5不能为0，所以cur=0这一行打上×。k = 0时，cur==aim的时候才为1，其他时候为0。

当cur==1时，每一行依赖左下这一行；当cur=5时，每一行依赖左上一行；当普遍位置时，每一格依赖左上和左下两格相加。

如下：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-75rqFqeJ-1648111812918)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1647826850975.png)]$

写出代码如下：

int ways3(int n, int cur, int aim, int k) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    dp[aim][0] = 1; //base case：初始化第0列

    for (int j = 1; j <= k; ++j) {
        dp[1][j] = dp[2][j - 1]; //cur=1依赖左下行
        for (int i = 2; i < n; ++i) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i + 1][j - 1];
        }
        dp[n][j] = dp[n - 1][j - 1]; //cur=k依赖左下格
    }

    return dp[cur][k];
}
int main() {
    cout << ways3(5, 4, 4, 6);
}
//打印结果为16

3.动态规划数组的空间压缩技巧（滚动数组）

经常遇到这样一个场景，做动态规划时，填一个二维表，填完二维表只需要右下角的值。如果用户只需要左下角的值，那么不需要申请整个表，可以用滚动数组来解决。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RvQczjL4-1657809884963)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652234786259.png)]$

适用滚动数组一般是如下依赖关系情况：

每个位置依赖于左边和上边的位置。我们可以用一行数组一行一行滚动得到最后一行的值。如用第二行得到第一行的值，f只依赖于a位置，因次滚动数组替换为fbcde。第二行第二列只依赖于其上和左的位置，即f和b元素，将b元素更新为g；第二行第三列依赖于g和c元素，将c更新为h，以此类推可以得到第二行的滚动数组。第三行以及后面行的滚动数组也以此类推可以得出。可以用以下代码表示：
```
//v[m][n]的任意位置依赖关系未v[m][n] = f(v[m][n - 1], v[m - 1][n])
int v[m][n]; //原本需要的二维数组
int g[n]; //一维滚动数组
//更新滚动数组得到最后一行最后一列的元素
for (int i = 1; i < m; ++i) {
    g[0] = f(0, g[0]);
    for (int j = 1; j < n; ++j) {
        g[j] = f(g[j - 1] ,g[j]); 
    }
}
```

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zebslzGh-1657809884964)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652234952848.png)]$

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9vToxLXW-1657809884964)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652235516585.png)]$

2.每个位置依赖上一行左边多个位置。由于不依赖于同一行的数据，用一行滚动数组从右往左更新。可以用以下代码表示：

//v[m][n]的任意位置依赖关系未v[m][n] = f(v[m - 1][n - 1], v[m - 1][n], v[m - 1][n]).
int v[m][n]; //原本需要的二维数组
int g[n]; //一维滚动数组
//更新滚动数组得到最后一行最后一列的元素
for (int i = 1; i < m; ++i) {
    for (int j = n - 1; n > 1; --j) {
        g[j] = f(g[j], g[j - 1], g[j - 2]);
    }
    g[1] = f(g[j], g[j - 1], 0);
    g[0] = f(g[0], 0, 0);
}

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WiD2A0Wg-1657809884964)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652236254471.png)]$

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-k4JElHF7-1657809884965)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652236472007.png)]$

3.每个位置依赖上、左上、左三个位置。用一个变量记住左上角的值即可更新。可以用以下代码表示：

//v[m][n]的任意位置依赖关系未v[m][n] = f(v[m][n - 1], v[m - 1][n - 1], v[m - 1][n]).
int v[m][n]; //原本需要的二维数组
int g[n]; //一维滚动数组
//更新滚动数组得到最后一行最后一列的元素
for (int i = 1; i < m; ++i) {
    int t = g[0];
    g[0] = f(0, 0, g[0]);
    for (int j = 0; j < n; ++j) {
        int t2 = g[j];
        g[j] = f(g[j - 1], t, g[j]);
        t = t2;
    }
}

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gaLg2Y6c-1657809884965)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652236786405.png)]$

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vxbLw0fN-1657809884965)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1652237219275.png)]$

4.暴力尝试（回溯）的模型

1.从左往右尝试模型

1.1 0-1背包问题

例题① 0 - 1背包问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

测试用例：w={3, 2, 4, 7}, v = {5, 6, 3, 19}, bag = 11.结果为25

1.暴力递归法

//当前考虑到了index号货物，从index出发往后所有货物都可以自由选择，返回最大价值
//做的选择不能超过最大背包容量
int maxValue(vector<int>& w, vector<int>& v, int bag, int index) {
    if (bag < 0) {
        return 0;
    }
    if (index == w.size()) { //没有货
        return 0;
    }
    //index没到最后，有货且bag有空间
    //不要当前的货
    int p1 = maxValue(w, v, bag, index + 1);
    int p2 = 0;
    if (bag - w[index] >= 0) {
        p2 = maxValue(w, v, bag - w[index], index + 1) + v[index];
    }
    return max(p1, p2);
}
int main() {
    vector<int> w{ 3, 2, 4, 7 };
    vector<int> v{ 5, 6, 3, 19 };
    int bag = 11;
    cout << maxValue(w, v, bag, 0);
    return 0;
}
//打印结果为25

2.画表改成动态规划

int maxValue(vector<int>& w, vector<int>& v, int bag) {
    int n = w.size();
    vector<vector<int>> dp(n + 1, vector<int>(bag + 1));
    //dp[n][...] = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < bag + 1; ++j) {
            int p1 = dp[i + 1][j];
            int p2 = 0;
            if (j - w[i] >= 0) {
                p2 = dp[i + 1][j - w[i]] + v[i];
            }
            dp[i][j] = max(p1, p2);
        }
    }
    return dp[0][bag];
}
int main() {
    vector<int> w{ 3, 2, 4, 7 };
    vector<int> v{ 5, 6, 3, 19 };
    int bag = 11;
    cout << maxValue(w, v, bag);
    return 0;
}
//打印结果为25

例题② 0 -1背包变形

给一个数组coins，每个元素表示一个硬币的面值，每一枚硬币只能用一次，给定一个target，求凑出target最少要用几枚硬币,如果不能凑出返回-1.

测试用例：coins[2, 7, 3, 5, 3],target = 10.结果为2.

1.暴力递归

//coins固定参数， target固定参数
//coins[index...]自由选择，组成rest这么多钱，最少的硬币数返回
int minCoins(vector<int> &coins, int index, int rest) {
    if (rest < 0) { 
        return -1;
    }
    if (rest == 0) {
        return 0;
    }
    //rest > 0
    if (index == coins.size()) {
        return -1;
    }
    //rest > 0 并且有硬币
    int p1 = minCoins(coins, index + 1, rest);
    int p2Next = minCoins(coins, index + 1, rest - coins[index]);
    if (p1 == -1 && p2 == -1) {
        return -1;
    } else if (p1 == -1 && p2 != -1){
            return p2Next + 1;
    } else if (p1 != -1 && p2 == -1) {
         return p1;  
    } else {
        return min(p1, p2Next + 1);
    }                    
}

2.动态规划

int minCoins(vector<int>& coins, int aim) {
    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
    for (int j = 1; j <= aim; ++j) {
        dp[n][j] = -1;
    }

    for (int i = n - 1; i >= 0; --i) {
        for (int j = 1; j <= aim; ++j) {
            int p1 = dp[i + 1][j];
            int p2 = (j - coins[i] >= 0) ? dp[i + 1][j - coins[i]] : -1;

            if (p1 == -1 && p2 == -1) {
                dp[i][j] = -1;
            }
            else if (p1 == -1 && p2 != -1) {
                dp[i][j] = p2 + 1;
            }
            else if (p1 != -1 && p2 == -1) {
                dp[i][j] = p1;
            }
            else {
                dp[i][j] = min(p1, p2 + 1);
            }

        }
    }
    return dp[0][aim];

}

1.2完全背包问题

例题③ 完全背包

一个数组coins，每个元素表示一种类型硬币的面值，每一种面值有无数枚硬币，给定一个aim，求有多少种方法数

测试用例：coins[3, 5, 1, 2],target = 20.

1.暴力递归

//可以自由使用coins[index...]所有货币
//需要搞定的钱数为rest
//返回找零的方法数
int paths(vector<int> &coins, int index, int rest) {
    if (index == coins.size()) {
        return rest == 0 ? 1 : 0;
    }
    //arr[index] 0张 1张...不要超过rest的钱数
    int ways = 0;
    for (int zhang = 0; coins[index] * zhang <= rest; ++zhang) {
        ways += paths(coins, index + 1, rest - coins[index] * zhang);
    }
    return ways;
}

2.动态规划（不优化）

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nk4AFHh2-1648111812919)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1648109691710.png)]$

int paths(vector<int> &coins, int aim) {
    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= aim; ++j) {
        	int ways = 0;
    		for (int k = 0; coins[i] * k <= j; ++k) {
        		ways += dp[i + 1][j - coins[i] * k];
    		}
       		dp[i][j] = ways;
        }
    }
    return dp[0][aim];
}

3.动态规划优化

填表的时候如果有枚举行为，可以利用观察的方式，试试邻近的位置能不能替代枚举行为，只与观察有关。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rRlJCn1M-1648111812919)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1648110331602.png)]$

int paths(vector<int> &coins, int aim) {
    int n = coins.size();
    vector<vector<int>> dp(n + 1, vector<int>(aim + 1));
    dp[n][0] = 1;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= aim; ++j) {
            dp[i][j] = dp[i + 1][j];
            if (j - coins[i] >= 0) {
                dp[i][j] += dp[i][j - coins[i]];
            }
        }
    }
    return dp[0][aim];
}

1.3子串和子数组问题（区分于子序列）

看到子串和子数组问题就立马想到以下模型：

//以index为结尾情况下，怎么怎么样。
//如：求字符串最长没有重复的子串
//以index为结尾，返回最长没有重复的子串长度
int process(string s, int index) {
    
}

例题④在一个字符串中找到没有重复字符子串中最长的长度

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-E0GPc2Ma-1657810483905)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1653363454946.png)]$

【递归代码】

//返回以index为结尾情况下，最长无重复子串长度
int process(string s, int index) {
    //瓶颈1：当前字符上次出现的位置。
    //瓶颈2：以index - 1为结尾最长子串开头位置。取最近位置的瓶颈
    if (s.size() == 0) {
        return 0;
    }
    if (index == 0) {
        return s[0];
    }
    int preIndex = index - process(s, index - 1);
    for (int i = index - 1; i >= preIndex; --i) {
        if (s[index] == s[i]) {
            return index - i + 1;
        }
    }
    return index - preIndex + 1;
}

【动态规划代码】

int maxSubStr(string& s) {
    if (s.size() == 0) {
        return 0;
    }
    if (s.size() == 1) {
        return 1;
    }
    int n = s.size();
    vector<int> dp(n);
    dp[0] = 1;
    int maxLen = 1;
    for (int i = 1; i < n; ++i) {
        int preIndex = i - dp[i - 1];
        int j = i - 1;
        for (; j >= preIndex; --j) {
            if (s[i] == s[j]) {
                dp[i] = i - j;
                maxLen = max(maxLen, dp[i]);
                break;
            }
        }
        if (j == preIndex - 1) {
            dp[i] = i - preIndex + 1;
            maxLen = max(maxLen, dp[i]);
        }
    }
    return maxLen;
}

1.4股票问题

看到股票问题立马想到以下模型模型：

//nums为每日股票的价格
//index为来到第index天
//hand表示第index天是否持有股票
//[0..index - 1]天已经考虑，[index...]自由选择，返回[index...]天获得股票的最大利润
int process(vector<int> &nums, int index, bool hand) {
    
}

1.5其他问题

例题⑤ 字符转换

规定1对应A、2对应B、3对应C...26对应Z。那么一个数字字符串比如"111"就可以转换成"AAA"、"KA"、"AK",给定一个只有数字字符组成的字符串str，返回有多少种转化结果。

测试用例："11111"，结果8

1.暴力法

//str[0..index - 1]不用过问
//str[index ....]去转换，返回有多少种转换方法
int count(const string& str, int index) {
    if (index == str.size()) { //前面的决定达到str.size()时构成了一个结果
        return 1;
    }
    //index没有到最后，说明有字符
    if (str[index] == '0') { //0不是一个有效的转化，说明之前的决定错了
        return 0;
    }
    //str[i] != 0
    //可能性1:index单转
    int ways = count(str, index + 1);
    //可能性2：后面两个字符构成的数字在[1, 26]之间可以转
    if (index + 1 < str.size() && (str[index] - '0') * 10 + str[index + 1] - '0' < 27) {
        ways += count(str, index + 2);
    }
    return ways;
}
int main() {
    cout << count("11111", 0);
}
//打印结果为8

2.画表改成动态规划

//str[0..index - 1]不用过问
//str[index ....]去转换，返回有多少种转换方法
int count(const string& str) {
    int n = str.size();
    vector<int> dp(n + 1);
    dp[n] = 1;
    for (int i = n - 1; i >= 0; --i) {
        int ways = dp[i + 1];
        if (i + 1 < n && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
            ways += dp[i + 2];
        }
        dp[i] = ways;
    }

    return dp[0];
}
int main() {
    cout << count("11111");
}
//打印结果为8

2.范围尝试模型

例题① 先手反手

给定一个整数arr，代表数值不同的纸牌排成一条线。玩家A和B依次拿走每张纸牌，规定玩家A先拿，B后拿，但是每个玩家只能拿走最左或者最后的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。

测试用例：[50, 100, 20, 10].结果先手：10， 100，结果110

1.暴力递归法

//先手函数
int s(vector<int>& nums, int left, int right);
int f(vector<int>& nums, int left, int right) {
    if (left == right) { //只剩一张牌，先手只能拿这一张牌
        return nums[left];
    }
    return max(nums[left] + s(nums, left + 1, right), nums[right] + s(nums, left, right - 1));
}

//后手函数
int s(vector<int>& nums, int left, int right) {
    if (left == right) { //只剩一张牌，无牌可拿
        return 0;
    }
    //对手先手，就是在对手选完一张牌后，我们在剩下的牌里先手
    return min(f(nums, left + 1, right), f(nums, left, right - 1));
}
int main() {
    vector<int> nums{ 50, 100, 20, 10 };
    cout << max(f(nums, 0, 3), s(nums, 0, 3));
}
//打印结果为110

2.记忆化搜索

int s(vector<int>& nums, int left, int right, vector<vector<int>>& fmap, vector<vector<int>>& gmap);
int f(vector<int>& nums, int left, int right, vector<vector<int>>& fmap, vector<vector<int>>& gmap) {
    if (fmap[left][right] != -1) {
        return fmap[left][right];
    }
    int res = 0;
    if (left == right) { //只剩一张牌，先手只能拿这一张牌
        res = nums[left];
    } else {
        res = max(nums[left] + s(nums, left + 1, right, fmap, gmap), nums[right] + s(nums, left, right - 1, fmap, gmap));
    }
    fmap[left][right] = res;
    return res;
}

//后手函数
int s(vector<int>& nums, int left, int right, vector<vector<int>>& fmap, vector<vector<int>>& gmap) {
    if (gmap[left][right] != -1) {
        return gmap[left][right];
    }
    int res = 0;
    if (left != right) {
        res = min(f(nums, left + 1, right, fmap, gmap), f(nums, left, right - 1, fmap, gmap));
    }
    gmap[left][right] = res;
    return res;
}
int main() {
    vector<int> nums{ 50, 100, 20, 10 };
    vector<vector<int>> fmap(4, vector<int>(4, -1));
    vector<vector<int>> gmap(4, vector<int>(4, -1));
    cout << max(f(nums, 0, 3, fmap, gmap), s(nums, 0, 3, fmap, gmap));
}
//打印结果为110

画表转换成动态规划

有两个表fmap和gmap，范围left永远都小于等于right，因此表的左下半都用不上打叉。fmap的格子依赖gmap的左和下两个格子，gmap的格子依赖fmap的左和下两个格子。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-412kEnG9-1648111812920)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1647849102502.png)]$

int win(vector<int>& nums) {
    if (nums.size() == 0) {
        return 0;
    }
    int n = nums.size();
    vector<vector<int>> fmap(n, vector<int>(n));
    vector<vector<int>> gmap(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        fmap[i][i] = nums[i];
    }
    for (int startCol = 1; startCol < n; ++startCol) {
        int i = 0;
        int j = startCol;
        while (j < n) {
            fmap[i][j] = max(nums[i] + gmap[i + 1][j], nums[j] + gmap[i][j - 1]);
            gmap[i][j] = min(fmap[i + 1][j], fmap[i][j - 1]);
            ++i;
            ++j;
        }
    }
    return max(fmap[0][n - 1], gmap[0][n - 1]);
}
int main() {
    vector<int> nums{ 50, 100, 20, 10 };
    cout << win(nums);
}
//打印结果为110

例题② 最长回文子序列

给定一个字符串str，返回这个字符串的最长回文子序列长度。

测试用例：str = “a12b3c43def2ghi1kpm”,最长回文子序列是"1234321"或者"123c321",返回长度为7.

思路1：一个字符串的最长回文子序列就是它和它的逆序串的最长公共子序列。

思路2：范围尝试模型

1.暴力递归

//str[L...R]的最长回文子序列长度返回
int f(string &str, int left, int right) {
    if (left == right) { //只有一个字符
        return 1;
    }
    if (left == right - 1) { //只有两个字符
        return str[left] == str[right] ? 2 : 1;
    }
    //既不以left开头也不以right结尾
    int p1 = f(str, left + 1, right - 1);
    //以left开头，不以right结尾
    int p2= f(str, left, right - 1);
    //不以left开头，以right结尾
    int p3 = f(str, left + 1, right);
    //既以left开头又以right结尾
    int p4 = str[left] == str[right] ? 2 + f(str, left + 1, right - 1) : 0;
    return max(p1, max(p2, max(p3, p4)));
}

2.动态规划

int f(string &str) {
    int n = str.size();
    vector<vector<int>> dp(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
    }
    for (int i = 0; i < n - 1; ++i) {
        if (str[i] == str[i + 1]) {
            dp[i][i + 1] = 2;
        } else {
            dp[i][i + 1] = 1;
        }
    }
    for (int startCol = 2; startCol < n; ++startCol) {
        for (int i = 0, j = startCol; j < n; ++i, ++j) {
            int p1 = dp[i][j - 1];
            int p2 = dp[i + 1][j];
            int p3 = str[i] == str[j] ? 2 + dp[i + 1][j - 1] : dp[i + 1][j - 1];
        }
    }
    return dp[0][n - 1];
}

例题③逻辑表达式组合问题

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VKr0UUTx-1657810694544)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1653360508118.png)]$

【思路】递归函数f(L, R, desire)表示在范围L，R上组合成desire结果有多少种方式。枚举[L, R]范围内每个逻辑符号是最后结合的情况下有多少种情况，再相加即可。

【暴力递归代码】

//假设给定的表达式都是有效的
//exp[L...R]返回期待值为desired的方法数
//潜台词：L R一定不要压中逻辑符号,即L，R都是偶数
int process(string &exp, bool desired, int L, int R) {
    //base case
    if (L == R) {
        if (exp[L] == '1') {
            return desired == 1 ? 1 : 0;
        } else {
            return desired == 0 ? 1 : 0;
        }
    }
    //L..R不止一个字符
    if (desired) { //期待值为true
        //枚举[L..R]上每一个逻辑符号都是最后结合的
        for (int i = L + 1; i < R; i += 2) {
            if (exp[i] == '&') {
                res += process(exp, true, L, i - 1) * process(exp, true, i + 1, R);
            } else if (exp[i] == '|') {
        		res += process(exp, true, L, i - 1) * process(exp, true, i + 1, R);
                res += process(exp, false, L, i - 1) * process(exp, true, i + 1, R);
                res += process(exp, true, L, i - 1) * process(exp, false, i + 1, R);
            } else { //exp[i] == '^',亦或
                res += process(exp, true, L, i - 1) * process(exp, false, i + 1, R);
                res += process(exp, false, L, i - 1) * process(exp, true, i + 1, R);
            }
        }
        
    } else { //期待为false
        //枚举[L..R]上每一个逻辑符号都是最后结合的
        for (int i = L + 1; i < R; i += 2) {
            if (exp[i] == '&') {
        		res += process(exp, false, L, i - 1) * process(exp, false, i + 1, R);
                res += process(exp, false, L, i - 1) * process(exp, true, i + 1, R);
                res += process(exp, true, L, i - 1) * process(exp, false, i + 1, R);
            } else if (exp[i] == '|') {
        		res += process(exp, false, L, i - 1) * process(exp, false, i + 1, R);
            } else { //exp[i] == '^',亦或
                res += process(exp, true, L, i - 1) * process(exp, true, i + 1, R);
                res += process(exp, false, L, i - 1) * process(exp, false, i + 1, R);
            }
        }
        
    }
    return res;
}

【动态规划代码】

int dpLive(string &exp, bool desired) {
    int n = exp.size();
    vector<vector<int>> tMap(n, vector<int>(n));
    vector<vector<int>> fMap(n, vector<int>(n));
    for (int i = 0; i < n; i += 2) {
        tMap[i][i] == exp[i] == '1' ? 1 : 0;
        fMap[i][i] == exp[i] == '0' ? 1 : 0;
    }
    //表从下往上从左往右填tmap
    for (int i = n - 3; i >= 0; i -= 2) {
        for (int k = i + 2; j < n; j += 2) {
            for (int k = i + 1; k < j; k += 2) {
                //根据递归填
            }
        }
    }
    //表从下往上从左往右填fmap
    for (int i = n - 3; i >= 0; i -= 2) {
        for (int k = i + 2; j < n; j += 2) {
            for (int k = i + 1; k < j; k += 2) {
                //根据递归填
            }
        }
    }
    return desired ? tMap[0][N - 1] : fMap[0][N - 1];
}

3.样本对应模型

3.1其他

例题①剪贴纸

给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文。arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。返回需要至少多少张贴纸可以完成这个任务，每一种贴纸都有无穷张。

测试用例：str = "babac", arr = {"ba", "c", "abcd"}.

至少需要两张贴纸"ba"和"abcd",因为使用这两张贴纸，把每一个字符单独剪开，含有2个a、2个b、1个c。是可以拼出str的。所以返回2.

1.暴力法

string mins(string& lhs, string& rhs) {
    int count[26] = { 0 };
    for (char c : lhs) {
        count[c - 'a']++;
    }
    for (char c : rhs) {
        count[c - 'a']--;
    }
    string res;
    for (int i = 0; i < 26; ++i) {
        while (count[i] > 0) {
            res += ('a' + i);
            --count[i];
        }
    }
    return res;
}
//所有贴纸stickers，每一种贴纸都有无穷张
//target
//最少张数
int minCount(vector<string>& stickers, string target) {
    if (target.size() == 0) {
        return 0;
    }
    int m = INT32_MAX;
    for (string first : stickers) {
        string rest = mins(target, first);
        if (rest.size() != target.size()) {
            m = min(m, minCount(stickers, rest));
        }
    }
    return m + (m == INT32_MAX ? 0 : 1);
}
int main() {
    vector<string> stickers{ "ba", "c", "abcd" };
    string target{"babac"};
    cout << minCount(stickers, target);
}
//打印结果为2

2.计划搜索版本

由于可变参数是string类型，无法做成表结构或者做成表结构特别麻烦，因此用计划搜索版本便是其动态规划版本。

string mins(string& lhs, string& rhs) {
    int count[26] = { 0 };
    for (char c : lhs) {
        count[c - 'a']++;
    }
    for (char c : rhs) {
        count[c - 'a']--;
    }
    string res;
    for (int i = 0; i < 26; ++i) {
        while (count[i] > 0) {
            res += ('a' + i);
            --count[i];
        }
    }
    return res;
}
//所有贴纸stickers，每一种贴纸都有无穷张
//target
//最少张数
int minCount(vector<string>& stickers, string target, unordered_map<string, int>& dp) {
    if (target.size() == 0) {
        return 0;
    }
    if (dp.find(target) != dp.end()) {
        return dp[target];
    }
    int m = INT32_MAX;
    for (string first : stickers) {
        string rest = mins(target, first);
        if (rest.size() != target.size()) {
            m = min(m, minCount(stickers, rest, dp));
        }
    }
    dp[target] = m + (m == INT32_MAX ? 0 : 1);
    return dp[target];
}
int main() {
    vector<string> stickers{ "ba", "c", "abcd" };
    string target{ "babac" };
    unordered_map<string, int> dp;
    cout << minCount(stickers, target, dp);
}
//打印结果为2

例题② 象棋问题

把象棋棋盘放入第一象限，棋盘的最左下角是(0, 0)位置，那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域，给你三个参数x、y、k，返回“马”从(0, 0)位置出发，必须走k步，最后落在(x, y)上的方法有多少种。

1.暴力递归

//当前来到的位置是(x, y)
//剩下rest步
//跳完rest步，跳到(a, b)的方法数有多少
int jump(int x, int y, int a, int b, int rest) {
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    if (rest == 0) {
        return (x == a && y == b) ? 1 : 0;
    }
    int p1 = jump(x + 2, y + 1, a, b, rest - 1);
    int p2 = jump(x + 1, y + 2, a, b, rest - 1);
    int p3 = jump(x - 1, y + 2, a, b, rest - 1);
    int p4 = jump(x - 2, y + 1, a, b, rest - 1);
    int p5 = jump(x + 2, y - 1, a, b, rest - 1);
    int p6 = jump(x + 1, y - 2, a, b, rest - 1);
    int p7 = jump(x - 1, y - 2, a, b, rest - 1);
    int p8 = jump(x - 2, y - 1, a, b, rest - 1);
    return p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;
}

2.动态规划

int pick(vector<vector<vector<int>>> &dp, int x, int y, rest) {
    if (x < 0 || x > 9 || y < 0 || y > 8) {
        return 0;
    }
    return dp[x][y][rest];
}
int jump(int a, int b, int k) {
    vector<vector<vector<int>> dp(10, vector<vector<int>>(9, vector<int>(k + 1)));
    dp[a][b][0] = 1;
    for (int rest = 1; rest <= k; ++rest) {
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < 9; ++j) {
                d[i][j][k] += pick(i + 2, j + 1, rest - 1);
                d[i][j][k] += pick(i + 1, j + 2, rest - 1);
                d[i][j][k] += pick(i - 1, j + 2, rest - 1);
                d[i][j][k] += pick(i - 2, j + 1, rest - 1);
                d[i][j][k] += pick(i + 2, j - 1, rest - 1);
                d[i][j][k] += pick(i + 1, j - 2, rest - 1);
                d[i][j][k] += pick(i - 2, j - 1, rest - 1);
                d[i][j][k] += pick(i - 1, j - 2, rest - 1);
            }
        }
    }
    return dp[0][0][k];
}

3.2最长公共子序列和最长公共子串问题

例题③最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

1.暴力递归

//只关心lhs[0...i]与rhs[0...j]的最长公共子序列多长
//返回长度
int longestCommonS(string &lhs, string &rhs, int i, int j) {
    if (i == 0 && j == 0) { //lhs和rhs都只有1个字符
        return lhs[i] == rhs[j] ? 1 : 0;
    } else if (i == 0) { //lhs只有一个字符
        if (lhs[i] == rhs[j]) {
            return 1;
        } else {
            return longestCommonS(lhs, rhs, i, j - 1);
        }
    } else if (j == 0) {
          if (lhs[i] == rhs[j]) {
            return 1;
        } else {
            return longestCommonS(lhs, rhs, i - 1, j);
        }
    } else { //i != 0 && j != 0
        //完全不考虑i结尾，可能考虑j结尾
        int p1 = longestCommonS(lhs, rhs, i - 1, j);
        //完全不考虑j结尾，可能考虑i结尾
        int p2 = longestCommonS(lhs, rhs, i, j - 1);
        //考虑i也考虑j
        int p3 = lhs[i] == rhs[j] ? (1 + longestCommonS(lhs, rhs, i - 1, j - 1)) : 0;
        return max(p1, max(p2, p3));
    }
    
}

2.改成动态规划

int longestCommonSubsequence(string &s1, string &s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m, vector<int>(n));
    for (int j = 0; j < n; ++j) {
        if (s2[j] == s1[0]) {
            dp[0][j] = 1;
        }
    }
    for (int i = 1; i < m; ++i) {
        if (s1[i] == s2[0]) {
            dp[i][0] = 1;
        }
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            int p1 = dp[i - 1][j];
            int p2 = dp[i][j - 1];
            int p3 = s1[i] == s2[j] ? (1 + dp[i - 1][j - 1]) : 0;
            dp[i][j] = max(p1, max(p2, p3));
        }
    }
    return dp[m - 1][n - 1];
}

3.3编辑距离

例题④编辑距离

给定两个字符串str1和str2，再给定三个整数ic、dc、rc分别代表插入、删除和替换一个字符的代价，返回将str1[0...i]编辑成str2[0...j]的最小代价。

测试用例str1 = “abc”, str2 = “adc”, ic = 5, dc = 3, rc = 2.返回2.

1.暴力递归

//s1前缀长度为i的字符串编辑成s2前缀长度为j的字符串最低代价为多少
int process(string s1, string s2, int i, int j, int ic, int dc, int rc) {
	if (i == 0 && j == 0) { //i和j都是空串，0代价
		return 0;
    }
    if (i == 0) { //s1是空串，编辑成s2只能插入
        return j * ic;
    }
    if (j == 0) { //s2是空串，编辑成s2只能删除
		return i * dc;
    }
    //s1、s2都不是空串
    //1.把s1[0...i - 1]编辑成s2并删除s1[i]的元素
    int p1 = process(s1, s2, i - 1, j, ic, dc, rc) + dc;
    //2.把s1编辑成s2[0...j - 1]并添加s2[j]的元素
    int p2 = process(s1, s2, i, j - 1, ic, dc, rc) + ic;
    //3.把s1[0...i - 1]编辑成s2[0..j - 1]并替换s1[i]变成s2[j]的元素
    //4.如果s1[i - 1] == s2[j - 1]，则无需替换.注意是i - 1和j - 1,因为i和j代表的是长度，而不是下标
    int p3 = s1[i - 1] == s2[j - 1] ? process(s1, s2, i - 1, j - 1, ic, dc, rc) : process(s1, s2, i - 1, j - 1, ic, dc, rc) + rc;
    return min(p1, min(p2, p3));
}

2.动态规划

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int j = 1; j <= n; ++j) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= m; ++i) {
        dp[i][0] = i;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int p1 = dp[i - 1][j] + 1;
            int p2 = dp[i][j - 1] + 1;
            int p3 = word1[i - 1] == word2[j - 1] ? dp[i - 1][j - 1] : dp[i - 1][j - 1] + 1;
            dp[i][j] = min(p1, min(p2, p3));
        }
    }
    return dp[m][n];
}

4.业务限制模型

有参数无法明确知道变化范围时，需要人为的估计出其范围。

例题①咖啡杯问题（业务限制模型）

给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间，给定一个整数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡。有一个洗碗机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯，每个咖啡杯也可以自己挥发干净，时间耗费为b，咖啡杯可以并行挥发。假设所有人拿到咖啡后立即喝干净，返回从开始等到所有咖啡机变干净的最短时间。

暴力法

class MyCompare {
public:
    bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs) {
        return (lhs.first + lhs.second) > (rhs.first + rhs.second);
    }
};

int minTime(vector<int> &arr, int n, int a, int b) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, MyCompare> que;
    for (int i = 0; i < arr.size(); ++i) {
        que.push(pair<int, int>{0, arr[i]};
    }
    vector<int> drinks;
    for (int i = 0; i < n; ++i) {
        pair<int, int> cur = que.top();
        que.pop();
        cur.first += cur.second;
        drinks.push_back(cur.first);
        que.push(cur);
    }
    //drinks为最优喝完咖啡时间，问题就变成了drinks[]数组表示喝完咖啡的时间，有一个洗碗机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯，每个咖啡杯也可以自己挥发干净，时间耗费为b，咖啡杯可以并行挥发。假设所有人拿到咖啡后立即喝干净，返回从开始等到所有咖啡机变干净的最短时间。             
    return process(drinks, a, b, 0, 0);
}
                 
//wash 洗一杯的时间（串行）
//air 咖啡自己挥发干净的时间（并行）
//free表示洗的机器何时可用
//drinks 每一个员工喝完的时间
//drinks[0..index - 1]都已经干净了不用你操心了
//返回drinks[index...]想变干净最少需要的时间。
int process(vector<int> &drinks, int wash, int air, int index, int free) {
    if (index == drinks.size()) { //没有杯子
        return 0;
    }
    //index号杯子 决定洗
    int selfClean1 = max(drinks[index], free) + wash;
    int restClean1 = process(drinks, wash, air, index + 1, selfClean1);
    int p1 = max(selfClean1, restClean1);
    //index号杯子决定挥发
    int selfClean2 = drinks[index] + air;
    int restClean2 = process(drinks ,wash, air, index + 1, free);
    int p2 = max(selfClean2, restClean2);
    return min(p1, p2);
}

2.动态规划

int process(vector<int> &drinks, int wash, int air) {
    int maxFree = 0;
   	for (int i = 0; i < drinks; ++i) {
        maxFree = max(maxFree, drinks[i]) + wash;
    }
    int n = drinks.size();
    vector<vector<int>> dp(n + 1, vector<int>(maxFree + 1));
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= maxFree; ++j) { 
            int selfClean1 = max(drinks[i], free) + wash;
            if (selfClean1 > maxFree) {
                continue;
            }
            int restClean1 = dp[i + 1][selfClean1];  
    		int p1 = max(selfClean1, restClean1);
            int selfClean2 = drinks[i] + air;
    		int restClean2 = dp[i + 1][j];
    		int p2 = max(selfClean2, restClean2);
        	dp[i][j] = min(p1, p2);
        }
    }
    return dp[0][0];
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)