「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )-LMLPHP

一、题目描述

解法一:记忆化搜索(区间DP)

#include <iostream>
using namespace std;

long long dp[35][35], n;
long long  dfs(int l, int r) {
	if (l >= r) return 1;
	if (dp[l][r]) return dp[l][r];
	for (int mid = l; mid < r; mid++) {
		dp[l][r] += dfs(l, mid) * dfs(mid + 1, r);
	}
	return dp[l][r];
}
int main() {
	while (cin >> n) {
		dfs(1, n);
		cout << dp[1][n] << endl;
	}
	return 0;
}

如果说简单的理解这个算法,我们可以打一段输出来检测每一次处理的dp数组的具体数值。
「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )-LMLPHP
也就是说,当n=4时,可以把问题看成:

14 = 11 * 24 + 12 * 34 + 13 * 44。

注意这是一个非常重要的点,有助于我们理解。

用dp[i][j]表示区间[i,j]的乘法方案数量,真正的核心点是考虑乘法发生在哪个划分点(切点)。然后不断的去更新这个数量并进行相加。

具体过程可以看成如下:

1. 初始化dp数组:
   - 创建一个二维数组dp[35][35],并将所有元素初始化为02. 调用dfs(1, 5)- 进入dfs函数,参数l=1,r=53. 判断基本情况:
   - l=1 小于 r=5,继续执行。

4. 判断是否已计算过:
   - dp[1][5]的值为0(初始值),继续执行。

5. 循环遍历分割点:
   - 初始化mid=l=1- 进入循环:
     - mid=1,计算dp[1][5] += dfs(1, 1) * dfs(2, 5)- 计算dfs(1, 1)- 进入dfs函数,参数l=1,r=1- 判断基本情况:l=1 等于 r=1,返回1- 返回结果1- 计算dfs(2, 5)- 进入dfs函数,参数l=2,r=5- 判断基本情况:l=2 小于 r=5,继续执行。
         - 判断是否已计算过:dp[2][5]的值为0(初始值),继续执行。
         - 循环遍历分割点:
           - 初始化mid=2- 进入循环:
             - mid=2,计算dp[2][5] += dfs(2, 2) * dfs(3, 5)- 计算dfs(2, 2)- 进入dfs函数,参数l=2,r=2- 判断基本情况:l=2 等于 r=2,返回1- 返回结果1- 计算dfs(3, 5)- 进入dfs函数,参数l=3,r=5- 判断基本情况:l=3 小于 r=5,继续执行。
                 - 判断是否已计算过:dp[3][5]的值为0(初始值),继续执行。
                 - 循环遍历分割点:
                   - 初始化mid=3- 进入循环:
                     - mid=3,计算dp[3][5] += dfs(3, 3) * dfs(4, 5)- 计算dfs(3, 3)- 进入dfs函数,参数l=3,r=3- 判断基本情况:l=3 等于 r=3,返回1- 返回结果1- 计算dfs(4, 5)- 进入dfs函数,参数l=4,r=5- 判断基本情况:l=4 小于 r=5,继续执行。
                         - 判断是否已计算过:dp[4][5]的值为0(初始值),继续执行。
                         - 循环遍历分割点:
                           - 初始化mid=4- 进入循环:
                             - mid=4,计算dp[4][5] += dfs(4, 4) * dfs(5, 5)- 计算dfs(4, 4)- 进入dfs函数,参数l=4,r=4- 判断基本情况:l=4 等于 r=4,返回1- 返回结果1- 计算dfs(5, 5)- 进入dfs函数,

解法二:

#include <iostream>
using namespace std;
long long cishu(int n) {
    long long dp[100][100] = {0};
    for (int i = 1; i <= n; i++) {
        dp[i][i] = 1;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = 0;

            for (int k = i; k < j; k++) {
            	//用dp[i][j] 表示区间[i,j]的乘法方案数,考虑最后一次乘法发生在哪里来划分子问题 
                dp[i][j] = dp[i][j] + (dp[i][k] * dp[k + 1][j]);
            }
        }
    }
    return dp[1][n];
}
int main() {
    int n;
    while(cin >> n){
        long long num = cishu(n);
        cout << num << endl;
    }
}

「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )-LMLPHP

迭代的思想有点难以理解,如果想弄明白的话,建议各位读者手推一遍算法过程。

总结

Hello,各位看官老爷们好,洲洲已经建立了CSDN技术交流群,如果你很感兴趣,可以私信我加入我的社群。

📝社群中不定时会有很多活动,例如每周都会包邮免费送一些技术书籍及精美礼品、学习资料分享、大厂面经分享、技术讨论、行业大佬创业杂谈等等。

📝社群方向很多,相关领域有Web全栈(前后端)、人工智能、机器学习、自媒体变现、前沿科技文章分享、论文精读等等。

📝不管你是多新手的小白,都欢迎你加入社群中讨论、聊天、分享,加速助力你成为下一个技术大佬!也随时欢迎您跟我沟通,一起交流,一起成长。变现、进步、技术、资料、项目、你想要的这里都会有

📝网络的风口只会越来越大,风浪越大,鱼越贵!欢迎您加入社群~一个人可以或许可以走的很快,但一群人将走的更远!

📝关注我的公众号(与CSDN同ID:程序员洲洲)可以获得一份Java 10万字面试宝典及相关资料!~

📝想都是问题,做都是答案!行动起来吧!欢迎评论区or后台与我沟通交流,也欢迎您点击下方的链接直接加入到我的交流社群!~ 跳转链接社区~

「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )-LMLPHP

11-11 06:06