前言
本文章主要面向算法初学者、蓝桥杯参赛者。
今天重温一手第十三届的统计子矩阵,搜索的时候发现了第十一届的矩阵题,然后看了下网上的文章,好家伙!全网对于此题没有高质量的文章和解答思路,全是贴个代码最多说一两句别的话,代码里注释都没几行,对于初学者而言简直是灾难, 下午整理了下思路,现在我会分享我的思路,以及如何从思路转变为代码。
一、从简单样例入手,解释为什么选择DP动态规划解法
原题大意如下:
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的数字比左边数字大,同一列中下边的数字比上边的数字大。一共有多少种方案?
答案很大,你只需要给出方案数除以 2020 的余数即可。
我们先别想解答2020个数,那个太漫长,我们可以先想想,如果我只需要排列几个数字,比如2个数呢,他们分别是1、2,这2个数分配到2行有什么结果呢?
1、2 ------两种排列,其中第一行2个第二行0个出现1次,第一行1个第二行1个出现1次
第一行:1、2 1
第二行:无 2如果是3个数字呢?1、2、3?
1、2、3 ------三种排列,第一行3个第二行0个数字出现1次,第一行2个第二行1个数字出现2次
第一行:1、2、3 1、2 1、3
第二行:无 3 24个数字?1、2、3、4?
1、2、3、4 ------六种排列,第一行4个第二行0个数字出现1次,第一行3个第二行1个数字出现3次,第一行2个第二行2个数字出现2次
第一行:1、2、3、4 1、2、3 1、2、4 1、3、4 1、2 1、3
第二行:无 4 3 2 3、4 2、4
乍一看,里面似乎蕴含着这么一种规律:前一种情况会作为后一种情况的基础,比如一开始的1、2到1、2、3到1、2、3、4,三个数字的1、2 + 3会出现在四个数字的1、2 + 3、4里,新加入的数字总是继承前一种结果,然后会“粘”在前一种情况的某一行的后面,判断合法后形成本次数字的结果。好像有点绕?看看下图吧
啊哈!现在看到这种规则,后一个结果由前一个结果得来的思路,恰恰符合动态规划DP的思路,一个一个结果继承,到最后就是想要的2020个数字的结果啦!
注意!千万不要陷进去找全部的数字排列,题目要找的是这2020个数字,每行装1010个数字的情况下一共有几个排列结果。第一行有1、2、3或者1、3、4,不用管是哪种排列,你应当都看成第一行有3个数字。这是我当初纠结了一会的点。
当第一行数字个数==第二行数字个数,说明最新的数加在了第二行,结果会与同等第一行数字但第二行数字个数-1的情况相同。
当第一行数字个数>第二行数字个数,说明可能是最新数字加在第一行或者第二行,都符合规则就加一起。
若第一行数字个数<第二行数字个数,非法,违反了题意直接毙掉。
动态状态方程:
i、j分别为第一行的数字和第二行的数字下,
当i == j,dp[i][j]=dp[i][j-1],
当i > j,dp[i][j] = dp[i-1][j] + dp[i][j-1]
二、答案与代码实现(C++)
#include<iostream>
using namespace std;
/*
dp[i][j] i为第一行的个数 j为第二行的数字个数
研究发现(其实是在纸上自己写):dp[2][1] = 2 dp[2][2] = 2 dp[3][0] = 1 dp[3][1] = 3 dp[3][2]=5
即当i>j dp[i][j] = dp[i-1][j] + dp[i][j-1]
而当i==j dp[i][j] = dp[i][j-1]
不存在i<j,因为题目规则限定了第一行一定不小于第二行的数字个数。
*/
// 小技巧: 把要开很大的数组放main外面不会把栈空间撑爆.
int dp[1011][1011];// 每一项初始值是0
int main() {
// 问题都是从小到大的,一开始排1个数,然后2个数,3个数...一直到排2020个数
// dp[i][j] i为第一行的数字个数,j是第二行的数字个数,规则为i>j或i==j
for (int i = 0; i <= 1010; i++) {
// dp[i][0] 就是数字只放第一行,被限制死了排序,只能一路都是 右>左,12345... 134...
// 所以只有1个排序结果
dp[i][0] = 1;
for (int j = 1; j <= 1010; j++) {
// 不存在i<j的情况
if (i < j) {
break;
}
if (i > j) {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 2020;
}
else if (i == j) {
dp[i][j] = dp[i][j - 1] % 2020;
}
}
}
// 答案输出
cout << "只有四个数的情况第一行2个第二行2个:" <<dp[2][2] << endl;
cout << "只有四个数的情况第一行3个第二行1个:" << dp[3][1] << endl;
cout << "只有四个数的情况第一行4个第二行0个:" << dp[4][0] << endl;
cout << "那么排列2020个数字下,按要求每一行都是1010个:" << dp[1010][1010] << endl;
return 0;
}
答案:1340
文章来源:https://www.toymoban.com/news/detail-415535.html
总结
人非圣贤,孰能无过,如果我的文章哪里有误或是解释不清楚,请您指正;亦或者您有什么不懂,欢迎留言评论呀,我会尽我所能解答。所有的评论、私信我都会定期查看并且回复。文章来源地址https://www.toymoban.com/news/detail-415535.html
到了这里,关于2020第11届蓝桥杯矩阵的真·详细题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!