摘要

本系列從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 1e9int 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;
}