如果一个问题可以用动态规划算法解决，则总是可以在多项式时间内解决的。
T F
1-2
最优二叉搜索树的根结点一定存放的是搜索概率最高的那个关键字。
F
1-3
用动态规划而非递归的方法去解决问题时，关键是将子问题的计算结果保存起来，使得每个不同的子问题只需要被计算一次。子问题的解可以被保存在数组或哈希散列表中。
T
D、在动态规划中，我们要推导出一个子问题的解与其他子问题解的递推关系。要将这种关系转换为自底向上的动态规划算法，我们需要以正确的顺序填写子问题解的表格，使得在解任一子问题时，所有它需要的子问题都已经被解决了。在下列关系式中，哪一个是不可能被计算的？ (2分)
A(i,j)=min(A(i?1,j),A(i,j?1),A(i?1,j?1))
A(i,j)=F(A(min{i,j}?1,min{i,j}?1),A(max{i,j}?1,max{i,j}?1))
A(i,j)=F(A(i,j?1),A(i?1,j?1),A(i?1,j+1))
A(i,j)=F(A(i?2,j?2),A(i+2,j+2))
2-2
C、给定递推方程 f
?i,j,k
?? =f
?i,j+1,k
?? +min
?0≤l≤k
?? {f
?i?1,j,l
?? +w
?j,l
?? }。
D、要通过循环解此方程，我们一定不能用下列哪种方法填表？ (2分)
for k in 0 to n: for i in 0 to n: for j in n to 0
for i in 0 to n: for j in 0 to n: for k in 0 to n
for i in 0 to n: for j in n to 0: for k in n to 0
for i in 0 to n: for j in n to 0: for k in 0 to n
2-3
切原木问题：给定一根长度为N米的原木；另有一个分段价格表，给出长度L=1,2,?,M对应的价格P
?L
?? 。要求你找出适当切割原木分段出售所能获得的最大收益R
?N
?? 。例如，根据下面给出的价格表，若要出售一段8米长的原木，最优解是将其切割为2米和6米的两段，这样可以获得最大收益R
?8
?? =P
?2
?? +P
?6
?? =5+17=22。而若要出售一段3米长的原木，最优解是根本不要切割，直接售出。
Length L 1 2 3 4 5 6 7 8 9 10
Price P
?L
?? 1 5 8 9 10 17 17 20 23 28
下列哪句陈述是错的？(3分)
此问题可以用动态规划求解
若N≤M，则有R
?N
?? =max{P
?N
?? ,max
?1≤i<N
?? {R
?i
?? +R
?N?i
?? }}
若N>M，则有R
?N
?? =max
?1≤i<N
{Ri+RN?M }算法的时间复杂度是O(N2 )
单调递增最长子序列
设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
#include <iostream>
using namespace std;
int dl(int a[], int b[],int n) {
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++)
{
if (a[j] < a[i]&& b[j]>b[i] - 1) {
b[i] = b[j] + 1;
}
}
}
int t = b[1];
for (int k = 0; k < n; k++)
{
if (b[k] > t) {
t = b[k];
}
}
return t;
}
int main() {
int n;
cin >> n;
int *a = new int[n];
int *b = new int[n]();//置为0；
for (int i = 0; i < n; i++) {
b[i]++;
}
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << dl(a, b, n);
system("pause");
}
租用游艇问题 （17 分）
题目来源：王晓东，《算法设计与分析》
长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n所需的最少租金。
#include <iostream>
int dp[100][100];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
scanf("%d",&dp[i][j]);
}
}
for(int k=2;k<n;k++)
{
for(int i=1;i<=n-k;i++)
{
int j=i+k;
for(int z=i+1;z<=j;z++)
{
int temp=dp[i][z]+dp[z][j];
if(dp[i][j]>temp)
dp[i][j]=temp;
}
}
}
printf("%d\n",dp[1][n]);
return 0;
}
原文：https://www.cnblogs.com/yucuiwencookies/p/9940444.html