大部分的算法题最后都来源于几个基本算法问题的叠加,因此,只要找到这道题的算法来源就可以很快解决。
但是,需要注意的是,题目中的变量定义往往是没有规律的,变量也没有固定含义,而我的熟悉的基本算法模板题的变量定义是有固定意义的。比如,最常见的背包问题中,n表示物品的个数,m表示总体积,N表示最大物品的个数,M表示最大背包的体积。w表示价值。如果两套变量定义混用的话,写代码时很容易因为变量定义不清导致思路混乱。正确的做法是,知道了某算法题背后的基本问题后,使用算法模板题的变量定义方式。并将所有原本题目中的概念一一转换为算法模板题的概念。比如装箱问题中,求得是最大能装下的体积,即剩余体积最小。这里的最大体积对应于背包问题的最大价值。同时,注意到装箱问题的每个箱子对应于背包问题的一个物品,同时,物品的体积和价值相同。
那么转换后的背包问题是:
for(int i = 1;i <= n;i++)
{
cin>>v;
w = v;
for(int j = m;j >= v;j--)
{
f[j] = max(f[j],f[j-v]+w);
}
}
cout<<f[j]<<endl;
从中可以发现,算法题看似千千万万,实际都是基本算法问题的叠加以及增加额外条件限制而已。因此,算法模板题一定要熟练。并且非常熟悉每个模板题里的概念、变量和对应关系。做题时,这样看出来背后的算法模板,就直接将概念和变量一一转换过去后,就可以快速背出答案。