摘要

本系列从6道经典的动态规划题入手，去理解动态规划的基本思路和想法，以及动态规划和递归记忆搜索法存在的某些联系，对于每道题目，我们将用两种方法去实现，这里讲解第一道题目，作个开头。

前言

我们知道，大部分的动态规划题目可以利用递归加记忆搜索法去完成，这两者的程序速度方面并没有较大的区别。

动态规划（DP）和记忆化搜索（也称为递归记忆）是两种解决复杂问题的常用技术，它们都利用了子问题的解来构建原问题的解。

动态规划是一种自底向上的方法，它首先解决子问题，然后基于子问题的解来解决更大的问题。动态规划通常使用一个表格来存储子问题的解，这样在需要时就可以直接查找，而不需要重新计算。因此，动态规划通常用于最优化问题，如最短路径问题、最大子序列和问题等。

记忆化搜索是一种自顶向下的方法，它从原问题开始，然后递归地解决子问题。当一个子问题被解决时，它的解将被存储起来，以便在后续需要时使用。记忆化搜索在处理具有重叠子问题的递归问题时非常有效。

在速度上，动态规划和记忆化搜索通常具有相似的时间复杂度，因为它们都利用了子问题的解来避免重复计算。然而，具体的速度可能会根据问题的特性以及实现的细节而有所不同。例如，对于某些问题，动态规划可能需要解决所有的子问题，而记忆化搜索则只需要解决那些实际上被用到的子问题。因此，对于这些问题，记忆化搜索可能会比动态规划更快。然而，对于其他问题，动态规划可能会有更好的性能，因为它可以更有效地利用存储的子问题解。

总的来说，选择使用动态规划还是记忆化搜索通常取决于问题的特性以及个人的编程风格和经验。

题目

1.钢条切割问题

题目描述

Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。
给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。

关于输入

第一行：n，表示购买的长钢条的长度。
接下来一行包含 n 个数字，第 i 个数字出售长为 i 的钢条的价格，即 pi。
其中 0 < n <= 3000，0 < pi <= 10000。

关于输出

输出仅一行，为最大的销售收益值 rn。

例子输入

7
1 5 8 9 10 17 17

例子输出

18

提示信息

注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。

解题思路

首先，我们从第一道题目先开始介绍一下动态规划的基本解题策略和方法：

动态规划（Dynamic Programming，简称 DP）是一种解决复杂问题的策略，主要用于优化问题，如求最大值、最小值或者计数问题等。下面是动态规划的基本思路和解决策略：

1. **确定状态**：在动态规划中，状态通常表示为一个或多个变量的组合，这些变量能够完全描述一个问题。例如，在背包问题中，状态可能是当前的重量和价值。

2. **确定状态转移方程**：状态转移方程是描述如何从一个状态到另一个状态的规则。在大多数情况下，这个规则是基于问题的特性和逻辑来确定的。例如，在最长公共子序列问题中，如果两个字符相等，那么最长公共子序列的长度就是前一个状态的长度加一；否则，最长公共子序列的长度就是前两个状态中较大的那个。

3. **确定边界条件**：边界条件描述了当问题降到最小规模时的解。例如，在斐波那契数列问题中，边界条件是第一项和第二项分别为1。

4. **计算并存储状态**：在动态规划中，一般会使用一个表格（一维、二维或者更高维度）来存储所有的状态。计算顺序通常是从边界条件开始，根据状态转移方程逐步计算出所有的状态。

5. **根据存储的状态得到最终结果**：在计算出所有的状态后，可以根据题目要求从存储的状态中得到最终的结果。

动态规划的关键是理解状态和状态转移方程的概念。一旦理解了这两个概念，就可以应用动态规划来解决各种各样的问题。在实际应用中，可能需要花费一些时间和思考来确定正确的状态和状态转移方程。

我们试着带着这些想法去审视本题，题目给出了两个信息：钢条的总长度和每一段特定长度的钢条的价钱。如果我们选用一个dp数组，我们先考虑一下自己需要几维的dp数组，入门阶段来说，一般我们考虑一维或者二维就可以了，这取决于我们给的状态能否完全描述一个问题（比如我上篇写的旅行商问题，由于状态过于复杂，我们采用了一种二进制压缩状态的方法作为dp数组的一个变量，用当前所在城市作为dp数组的第二个变量，以此来构建整个问题）。

对于这个钢条切割的问题，其实根据题目给的信息，又由于钢条是连续的，长度的价格也是连续的，所以一个变量即可比较好的描述我们的问题的，我们这样定义，dp[n]表示，切割n长度的钢条可以获得的最大收益。

接下来，让我们先去想想转移方程，要切割n长度的钢条，我们是不是可以选择先切割一长度下来，再切割[n-1]长度的钢条？或者说，先切割k长度的钢条，再切割[n-k]长度钢条？其中k=1,2,3.....,n。这样，为求出最大的价钱，我们可以利用以下的动态规划转移方程：

dp[n]=max{dp[n-1]+p[1],dp[n-2]+p[2],......,dp[0]+p[n]}。

再来定义一下边界条件，显然,dp[0]=0,切割0长度的钢条自然一分钱没有。

这样的转移方程合理吗？能推导出最终的答案吗？如果能，又怎么用程序去实现？

首先，为了完成这个过程，一个循环是不太够的，我们需要用两层循环，外层循环控制一个变量k，表示先切割k长度的钢条下来，因为对于每个长度的钢条我们需要比较的次数是不一样的，第二层循环用一个变量j，表示当前对j长度的钢条操作，当j为[1]时，我们只需要比较一次，就是dp[1],当j为2时，我们会比较两次，dp[2-1]+p[1] 和dp[2-2]+p[2]，当j=3时，我们会比较三次,dp[3-1]+p[1] dp[3-2]+p[2],dp[3-3]+p[0],以此类推，而且由于我们是从低往高处推导的，所以，对于n=n-1时候，命题成立，我们可以推出对于n时命题也成立，而且经过我们的验证，n=1和n=2时都满足题意，故，这样的算法是可行的。

问题一dp代码展示

#include <iostream>
using namespace std;
#define INF 1e9

int p[3005];
int dp[3005];

int main() {
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=-INF;
    }
    dp[0]=0;
    for(int k=1;k<=n;k++)
        for(int j=k;j<=n;j++){
            dp[j]=max(dp[j],dp[j-k]+p[k]);
        }
    cout<<dp[n]<<endl;
    return 0;
}

这里再附上使用记忆搜索法加递归函数的方法的代码：

定义f(n)表示切割n长度钢条能得到的最大收益

#include <iostream>
using namespace std;

int p[3005];
int dp[3005];

int f(int n){
    if(n<=0){
        return 0;
    }
    if(dp[n]!=-1){
        return dp[n];
    }
    for(int k=1;k<=n;k++){
       dp[n]=max(dp[n],f(n-k)+p[k]);
    }
    return dp[n];
}

int main() {
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=-1;
    }
    cout<<f(n)<<endl;
    return 0;
}