石子合并问题

问题背景

(105条消息) dp算法 - 石子合并问题_lost_tower的博客-CSDN博客_石子合并

他的这个收算法解释的，但是我们保证我写的是我自己思考出来的。

这里我只是借用他的写出来的问题

问题分析

这个是思考这个题时候的笔记，有手推过程，以及递推公式

---

手推过程

算法实现

package com.dwx.passage3;

public class demo3__3 {
    private int m[];//m数组说是用来存放石头的
    private int dp[][];//用来存放合并后的石头堆
    private int i;//起始地址
    private int j;//终止地址

    int inf = 9999;

    public int[] getM() {
        return m;
    }

    public void setM(int[] m) {
        this.m = m;
    }

    public int[][] getDp() {
        return dp;
    }

    public void setDp(int[][] dp) {
        this.dp = dp;
    }

    public int getI() {
        return i;
    }

    public void setI(int i) {
        this.i = i;
    }

    public int getJ() {
        return j;
    }

    public void setJ(int j) {
        this.j = j;
    }


    //这个是动态规划方法的主体
    //这个递归程序用来求最小代价
    public void demoMin(){
        //对程序进行初始化
        //计算石头的数量
        int n = m.length;
        //不需要任何的初始化
        //初始化 都化为0
        for (int d = 1;d<n;d++){
            for (int e=1;e<n;e++){
                dp[d][e] = 0;
            }

        }

        //对除了对角线以外的数据进行操作
        //这里 我们设a为列，b为行,c为间断点
        //因此 我们的思想是 从a合并到b，以c为间断点
        int a,b,c;
        int min;
        for (b=2;b<m.length;b++){
            for (a=b-1;a>=1;a--){
                min = inf;
                //设置间断点
                for (c=b-1;c>=a;c--){
                    if (dp[a][c]+dp[c+1][b]+getNumber(a,b) < min){
                           min = dp[a][c]+dp[c+1][b]+getNumber(a,b);
                    }
                }
                dp[a][b] = min;
            }
        }
    }
    //这个程序用来求最大代价
    public void demoMax(){
        //对程序进行初始化
        //计算石头的数量
        int n = m.length;
        //不需要任何的初始化
        //初始化
        for (int d = 1;d<n;d++) {
            for (int e = 1; e < n; e++) dp[d][e] = 0;


        }        //对除了对角线以外的数据进行操作
        //这里 我们设a为列，b为行,c为间断点
        //因此 我们的思想是 从a合并到b，以c为间断点
        int a,b,c;
        int max;
        for (b=2;b<m.length;b++){
            for (a=b-1;a>=1;a--){
                max = 0;
                //设置间断点
                for (c=b-1;c>=a;c--){
                    if (dp[a][c]+dp[c+1][b]+getNumber(a,b) > max){
                        max = dp[a][c]+dp[c+1][b]+getNumber(a,b);
                    }
                }
                dp[a][b] = max;
            }
        }
    }

    //这个是获得合并后石头数量的方法
    public int getNumber(int i,int j){
        int number = 0;
        for (int k=i;k<=j;k++){
            number = number+m[k];
        }

        return number;
    }
}

检验

import com.dwx.passage3.demo3__3;

public class demo3_3Test {
    public static void main(String[] args) {
        //设置数组
        int[] m = new int[]{0,5,8,2,9,3,6,4};
        //设置dp数组
        int[][] dp = new int[m.length][m.length];
        // 设置起始位置和终止位置
        int i = 0;
        int j = 0;
        demo3__3 demo3__3 = new demo3__3();
        demo3__3.setDp(dp);
        demo3__3.setI(i);
        demo3__3.setJ(j);
        demo3__3.setM(m);
        //执行找最小代价程序
        demo3__3.demoMin();
        int[][] dp1 = demo3__3.getDp();
        for (int[] ints : dp1) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
        System.out.println("==============================");
        //执行找最大代价的程序
        demo3__3.demoMax();
        int[][] dp2 = demo3__3.getDp();
        for (int[] ints : dp2) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }

    }
}

输出结果

0	0	0	0	0	0	0	0	
0	0	13	25	48	64	85	106	
0	0	0	10	29	44	65	83	
0	0	0	0	11	25	40	57	
0	0	0	0	0	12	27	44	
0	0	0	0	0	0	9	22	
0	0	0	0	0	0	0	10	
0	0	0	0	0	0	0	0	
==============================
0	0	0	0	0	0	0	0	
0	0	13	28	54	81	114	151	
0	0	0	10	30	52	80	112	
0	0	0	0	11	26	50	76	
0	0	0	0	0	12	30	52	
0	0	0	0	0	0	9	23	
0	0	0	0	0	0	0	10	
0	0	0	0	0	0	0	0	

可以看到这个结果和我们的手推的dp矩阵时一致的，因此是一个合适的答案

不足之处

在编写动态规划问题的时候，思考最多的是地推公式，应该仔细分析，得到一个正确的递归公式。

得到递归公式也不代表是解决了这个问题，要分析好这个三重for循环怎么写，算法实现怎么写。

一定要注意，动态规划自底而上的原则

在分析递推公式的时候一定要注意：

dp[i] [j]矩阵的i和j到底代表着什么

Donate