面试题7---剪绳子详解

1.题目

给你一根长度为n的绳子，请把绳子剪成m段（m,n都是整数，n>1并且m>1）,每段绳子的长度记为k[0],k[1],…k[n]。请问k[0]乘k[1]乘…k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

2.涉及知识点

动态规划

基本思想：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解决这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但他们具有相同的填表格式。（以上说明来自百度百科）。
上文翻译：当你遇到一个问题，并想要得到它的解1，但这个问题可以拆成许多小问题，你想要得到解1，就必须得到小问题的解2，解3。同理，这些小问题可以拆成许多小小问题，你想要得到解2，解3，就必须得到小小问题的解4，解5，解6…。而且除了最后的一层，其它所有获取解的方法相同。因为当你获取一个解之后，下次再利用时就不需要重复计算，只需将这个解存储起来，下次直接调用，可大大减少时间复杂度。
这里通过一个实例来加深对动态规划的理解，经典的数字三角形问题
题目描述：在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。
分析解答：为了方便代码书写，我们可以将上述三角形用二维数组存储为如下形式。
可以看出每走第n行第m列时有两种后续：向下或者向右下，只有最后一行可以直接确定，当做边界条件，所以我们自然而然想到递归求解。
解题思路：

• 用二维数组存放数字三角形，D(r,j):第r行第j个数字（r,j从1开始计算）。MaxSum(i,j):从D(r,j)到底边的各条路径中，最佳路径的数字之和。问题：求MaxSum(1,1)。
• 典型的递归问题，从D(r,j)出发，下一步只能走D(r+1,j)或者D(r+1,j+1)。故对于N行的三角形：

if(r==N)MaxSu(r,j)=D(r,j);
elseMaxSum(r,j)=Max{MaxSum(r+1,j),MaxSum(r+1,j+1)}+D(r,j)

完整代码：

#include
#include
#define MAX 101
using namspace std;
int D[MAX][MAX];
int n;
int MaxSum(int i,int j)
{if(i==n)return D[i][j];int x=MaxSum(i+1,j);int y=MaxSum(i+1,j+1);return max(x,y)+D[i][j];
}
int main()
{int i,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>D[i][j];cout<<MaxSum(1,1)<<endl;
}

其实仔细观察，上述方法虽然看起来简单，但时间复杂度是非常大的，对很多位置都进行了不必要的计算，既然是不必要，那么我们就有方法去舍去那些不必要的计算，用一个辅助空间来保存已经计算过的数据即可，下面对上述代码加以改进。

#include
#include
#define MAX 101
using namspace std;
int D[MAX][MAX];
int maxSum[MAX][MAX];
int n;
int MaxSum(int i,int j)
{if(maxSum[i][j]!=-1)return maxSum[i][j];if(i==n)return D[i][j];int x=MaxSum(i+1,j);int y=MaxSum(i+1,j+1);return max(x,y)+D[i][j];
}
int main()
{int i,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++){cin>>D[i][j];maxSum[i][j]=-1;}cout<<MaxSum(1,1)<<endl;
}

既然可以用递归的思想写出来，我们都知道，递归一般情况下是可以转化为递推的，请看下面代码。

#include
#include
#define MAX 101
using namspace std;
int D[MAX][MAX];
int maxSum[MAX][MAX];
int n;
int main()
{int i,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>D[i][j];
for(i=1;i<=n;i++)maxSum[n][i]=D[n][i];
for(i=n-1;i>=1;i--)
{for(j=1;j<=i;j++)maxSum[i][j]=max(maxSum[i+1][j],maxSum[i+1][j+1])+D[i][j];
}
cout<<maxSum[1][1]<<endl;
}

这就是标准的动态规划解题过程。

3.就题论题

首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有n-1种可能的选择，也就是剪出来的第一段绳子的可能长度分别为1,2…,n-1.因此f(n)=max(f(i)乘f(n-i)),其中0 当绳子的长度为2时，只可能剪成长度为1的两段，因此f(2)等于1，当绳子的长度为3时，可能把绳子剪成长度分别为1和2的两段或者长度都为1的三段，由于1乘2>1乘1乘1，因此f(3)=2。下面是这一思路对应的参考代码。

int maxProductAfterCutting_solution(int length)
{if(length<2)return 0;if(length==2)return 1;if(length==3)return 2;int* products=new int[length+1];products[0]=0;products[1]=1;products[2]=2;products[3]=3;int max=0;for(int i=4;i<=length;i++){max=0;for(int j=1;j<=i/2;j++){int product=products[j]*productis[i-j];if(max<product)max=product;products[i]=max;}}max=products[length];delete[] products;return max;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！