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

这篇具有很好参考价值的文章主要介绍了「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

😎 作者介绍:我是程序员洲洲,一个热爱写作的非著名程序员。CSDN全栈优质领域创作者、华为云博客社区云享专家、阿里云博客社区专家博主、前后端开发、人工智能研究生。公粽号:程序员洲洲。
🎈 本文专栏:本文收录于洲洲的《算法小记》系列专栏,该专栏记录了许多常见的各种各样有趣的实战技巧。欢迎大家关注本专栏~专栏一键跳转
🤓 同时欢迎大家关注其他专栏,我将分享Web前后端开发、人工智能、机器学习、深度学习从0到1系列文章。
🌼 同时洲洲已经建立了程序员技术交流群,如果您感兴趣,可以私信我加入我的社群~社群中将不定时分享各类福利
🖥 随时欢迎您跟我沟通,一起交流,一起成长、进步!点此即可获得联系方式~

一、题目描述

题目描述:
设 A1, A2, …, An 为连续相乘的矩阵序列,矩阵相乘满足乘法结合律,那么一共有多少种相乘的方案?

比如 A1, A2, A3, A4 ,通过加括号来体现乘顺序,有 5 种方案:

((A1A2)A3)A4
(A1A2)(A3A4)
A1(A2(A3A4))
(A1(A2A3))A4
A1((A2A3)A4)

输入:
每组数据给出 1 ≤ n ≤ 30。
输出:
n 个矩阵的矩阵链相乘方案数。
输入5,则输出14。
输入10,则输出4862。

解法一:记忆化搜索(区间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++ ),算法小记,项目踩坑,算法,矩阵,动态规划
也就是说,当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++ ),算法小记,项目踩坑,算法,矩阵,动态规划

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

总结

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

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

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

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

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

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

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

「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ ),算法小记,项目踩坑,算法,矩阵,动态规划文章来源地址https://www.toymoban.com/news/detail-751962.html

到了这里,关于「算法小记」-2:矩阵链相乘的方案数【迭代/递归/动态规划/区域化DP/记忆化搜索】(C++ )的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划--矩阵链相乘问题

    明确原始问题A[1:n]: 计算矩阵链 所需的 最小乘法次数。 (1)是否满足最优子结构,问题的解是否包含子问题的优化解? 若计算A[1:n]的优化顺序在 k 处断开矩阵链,即A[1:n]=A[1:k]×A[k+1:n],则在A[1:n]的优化顺序中,对应于子问题A[1:k]的解必须是A[1:k]的优化解,对应A[k+1:n]的解必

    2024年01月25日
    浏览(46)
  • 矩阵链相乘(动态规划法)

    矩阵链乘法是耳熟能详的问题了,有很多矩阵,排列成矩阵链,矩阵链的要求是相邻的两个是可以相乘的,可以相乘是有条件的,两个矩阵能够相乘的条件就是行、列之间是有关系的,两个矩阵如果能够相乘,就是前面矩阵的列号和后面矩阵的行号是一致的。 如何确定矩阵的

    2024年02月09日
    浏览(49)
  • 矩阵链相乘的乘法次数(动态规划)

    该题是算法动态规划练习题 该题首先要清楚地认识和理解题意 首先,理解一次矩阵乘法会产生多少次乘法运算 例如给定两个矩阵(10 * 5)与(5 * 20) 会产生的乘法次数为 10*5*20=1000次 然后我们要理解当存在多个矩阵相乘时,乘的顺序不同,最终乘法运算的总次数也是不同的

    2024年01月25日
    浏览(38)
  • 7-1 矩阵链相乘问题 (20 分)(思路+详解+题目解析) 动态规划做法

    2:关于本题的矩阵乘法和递推方程的得出 3:实例演示 三:思路 =================================================================== 思路:这里在考虑的的时候,因为是多个矩阵相乘,求的最小乘法次数, 比如 A1_A2_A3_A4, 那么根据划分的不同,那么其乘法顺序也会不同,继而所求的乘法次数

    2024年04月09日
    浏览(76)
  • 0-1背包问题(Knapsack Problem)-动态规划方法(C语言递归和迭代)

    前言 背包0-1问题属于典型的求最大/最小子集问题范畴,它不像rod-cutting或matrix-chain-multiplication等问题,求解过程是按照单位等增或单位递减,0-1背包问题属于在集合范围内的某一个值,而且这些值大概率不是连续值。 问题描述 假定有N件物品,每件物品具有特定的价值value

    2024年02月06日
    浏览(43)
  • 算法12.从暴力递归到动态规划5

    题意:假设有排成一行的N个位置记为1~N,N一定大于或等于2 开始时机器人在其中的M位置上(M一定是1~N中的一个) 如果机器人来到1位置,那么下一步只能往右来到2位置; 如果机器人来到N位置,那么下一步只能往左来到N-1位置; 如果机器人来到中间位置,那么下一步可以往左

    2024年02月20日
    浏览(43)
  • 算法27:从暴力递归到动态规划(2)

    上一题比较简单,下面来一道比较难的题目。 假设有排成一行的 N 个位置,记为 1~ N , N 一定大于或等于 2 开始时机器人在其中的 M 位置上 ( M 一定是 1~ N 中的一个 ) 如果机器人来到 1 位置,那么下一步只能往右来到 2 位置; 如果机器人来到 N 位置,那么下一步只能往左来到

    2024年02月09日
    浏览(38)
  • 算法|9.从暴力递归到动态规划2

    题意:规定1和A对应、2和B对应、3和C对应…26和Z对应,那么一个数字字符串比如\\\"111”就可以转化为:“AAA”、“KA\\\"和\\\"AK” 给定一个只有数字字符组成的字符串str,返回有多少种转化结果 解题思路: 边界判断1:能够不被阻挡的走到最后,说明这个决策正确,返回1 边界判断2:0不

    2024年02月03日
    浏览(41)
  • 算法8.从暴力递归到动态规划1

    目前感觉,背包问题和货币数组问题本质相同,货币的与dp相关的三种代码写完了,快复习不完了,背包暂时先不写了,回头再写,补充,再总结,结合那个C++大神的文章再弄。 目前来讲,我接触到的背包问题有四种分别是01背包、完全背包、多重背包、以及部分背包。背包

    2024年02月07日
    浏览(37)
  • 算法7.从暴力递归到动态规划0

    题意:打印n层汉诺塔从最左边移动到最右边的全部过程 解题思路: 把字母抛掉,变成左中右三个盘子 多个盘子能一下到吗?不能,把上边的拿走,最下边的才能放到指位置(leftToRight) 上边的怎么拿,leftToMid。那它具体怎么拿,midToLeft…如此,需要6个子过程 他们之间互相调

    2024年02月08日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包