插入乘號
題目描述
給定一個非負整數，用k個乘號將其分割，使得乘積最大。
例如：在整數12345中插入兩個乘號，有以下插入法：
1*2*345 1*23*45 1*234*5
12*3*45 12*34*5
123*4*5
其中最大值是123*4*5 = 2460
關于輸入
一行兩個非負整數，非負整數s（s ≦ 10^9）和乘號的個數k（0 ≦ k < s的位數）。
輸入保證，如果按題目要求的乘法操作，不會使int發生溢出。
關于輸出
一行一個整數，即乘積的最大值
例子輸入
12345 2
例子輸出
2460
解題分析
動態規劃能夠解決的問題，一般可看出解決此問題需要解決的子問題，本題中，題目給出了兩個信息，一個是一個非負整數，另一個是插入的乘號的數量，我們需要想想，本題的dp數組應該如何去定義？一維還是二維？這取決于，我們能用幾個狀態來描述清楚問題。
再來復習一下動態規劃的基本思路：
動態規劃（Dynamic Programming，簡稱 DP）是一種解決復雜問題的策略，主要用于優化問題，如求最大值、最小值或者計數問題等。下面是動態規劃的基本思路和解決策略：
1. **確定狀態**：在動態規劃中，狀態通常表示為一個或多個變量的組合，這些變量能夠完全描述一個問題。例如，在背包問題中，狀態可能是當前的重量和價值。
2. **確定狀態轉移方程**：狀態轉移方程是描述如何從一個狀態到另一個狀態的規則。在大多數情況下，這個規則是基于問題的特性和邏輯來確定的。例如，在最長公共子序列問題中，如果兩個字符相等，那么最長公共子序列的長度就是前一個狀態的長度加一；否則，最長公共子序列的長度就是前兩個狀態中較大的那個。
3. **確定邊界條件**：邊界條件描述了當問題降到最小規模時的解。例如，在斐波那契數列問題中，邊界條件是第一項和第二項分別為1。
4. **計算并存儲狀態**：在動態規劃中，一般會使用一個表格（一維、二維或者更高維度）來存儲所有的狀態。計算順序通常是從邊界條件開始，根據狀態轉移方程逐步計算出所有的狀態。
5. **根據存儲的狀態得到最終結果**：在計算出所有的狀態后，可以根據題目要求從存儲的狀態中得到最終的結果。
動態規劃的關鍵是理解狀態和狀態轉移方程的概念。一旦理解了這兩個概念，就可以應用動態規劃來解決各種各樣的問題。在實際應用中，可能需要花費一些時間和思考來確定正確的狀態和狀態轉移方程。
對于我們現在面臨的問題，可以發現的，我們這樣去定義dp數組，用兩個變量來描述清楚問題，dp[i][j]，其中，i表示我們想要處理的數字的前i位，而j表示我們想要插入的乘號的數量。
轉移方程呢？怎么去書寫？
首先我們需要一個函數去幫助我們去對輸入的整數進行分割，sub(i,j)表示從i位置到j位置的切割數字。
接下里，我們可以把問題化小，對于dp[i][j]即在前i個字符內插入j個乘號，問題等價于，我們從k=j位置開始（因為要插入j-1個乘號），在前k個位置先插入j-1個乘號，再把最后一個乘號放在第k個位置，然后不斷增加k直至k到i-1位置，所以，我們有,dp[i][j]=max(dp[j][j-1]*sub(j,i-1),dp[j+1][j-1]*sub(j+1,i-1).....dp[i-1][j-1]*sub(i-1,i-1))，這個過程可以通過循環實現。
dp代碼實現如下
#include <iostream>
#include <cstring>
using namespace std;char num[10];
int k;
int dp[10][10]={0};int sub(int i,int j){int ans=0;while(i<=j){ans=ans*10+num[i]-'0';i++;}return ans;
}int main() {cin>>num>>k;int len=strlen(num);for(int i=1;i<=len;i++){for(int j=0;j<=i-1 && j<=k;j++){if(j==0){dp[i][j]=sub(0,i-1);}else{for(int k=j;k<=i-1;k++){dp[i][j]=max(dp[i][j],dp[k][j-1]*sub(k,i-1));}}}}cout<<dp[len][k]<<endl;return 0;
}
記憶搜索法結合遞歸代碼實現如下
我們定義f(i,j)為在前i個位置插入j個乘號得到的最大值。
#include <iostream>
#include <cstring>
using namespace std;char num[10];
int dp[10][10]={0};int sub(int i,int j){int ans=0;while(i<=j){ans=ans*10+num[i]-'0';i++;}return ans;
}int f(int i,int j){if(dp[i][j]){return dp[i][j];}if(j==0){return dp[i][j]=sub(0,i-1);}for(int k=j;k<=i-1;k++){dp[i][j]=max(dp[i][j],f(k,j-1)*sub(k,i-1));}return dp[i][j];
}int main() {int k;cin>>num>>k;int len=strlen(num);cout<<f(len,k)<<endl;return 0;
}
