题解 1602: 蓝桥杯算法训练VIP-乘积最大（JAVA）

解题思路:

给出两种解题思路

1. dfs暴力搜索即可

2. 动态规划

注意事项:

dfs解题时思路就是不断向后枚举乘号出现的位置，注意边界条件和递归结束条件即可。

动态规划解题：

    定义：令dp[i][j]为前i个数字，使用j个乘号时得到的最大值。

    转移方程：dp[i][j] = max(dp[i][j], dp[m][j+1]+num[m, i])（m<i），其中num[m，i]为数字字符串下标m到j的子串对应的数字。

                    (说实话并不太会证明该问题的最优子结构= - =)   

    最终返回dp[N][K]即为所求。

    其实就是考虑在使用j-1个乘号时所有的历史最大历史数字串

参考代码:

import java.io.*;
import java.util.*;

// https://www.dotcpp.com/oj/problem1602.html
// 法1 暴力dfs
// 法2 动态规划
public class Main {
    static BufferedReader cin;
    static PrintWriter out;
    static int N;
    static int K;
    static String numStr;
    public static void main(String[] args) throws IOException{
        cin = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        String[] line = cin.readLine().split(" ");
        N = Integer.parseInt(line[0]);  // 长度为N
        K = Integer.parseInt(line[1]);  // 使用K个乘号
        numStr = cin.readLine();
        out.println(numStr.substring(0, 0));
        out.println(dfs(0, 1, 0, 1));
        out.println(DP());
        out.flush();
        out.close();
    }

    static long dfs(int s, int e, int count, long res){  // 当前开始结束下标, 选取总数, 当前左侧结果
        if(count == K){
            return res*Long.parseLong(numStr.substring(s));
        }
        if(e == numStr.length())
            return -1;
        long res1 = dfs(e, e+1, count+1, res*Long.parseLong(numStr.substring(s, e)));  // 添加乘号
        long res2 = dfs(s, e+1, count, res); // 不在e下标下添加乘号
        return Math.max(res1, res2);
    }

    static long DP(){
        // dp[i][j]表示i个字母, j个乘号时最大乘积
        long[][] dp = new long[N+1][K+1];  // dp数组
        for(int i = 1;i < N+1; i++){
            dp[i][0] = Long.parseLong(numStr.substring(0, i));
        }
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= K && j<i; j++){  // 乘号个数严格小于数字个数
                for(int m = 1; m < i; m++){
                    dp[i][j] = Math.max(dp[i][j], dp[m][j-1]*Long.parseLong(numStr.substring(m, i)));
                }
            }
        }
        return dp[N][K];


    }

}