切木料(DP)问题

有一个长为L的木料需要割开,切的位置在一个数组里A[0…N],从一个地方切开的
cost是当前所切木料的长度。按不同的顺序切割,得到的total cost是不一样的,问怎
么切cost最
小。

我对题意的理解是,比如一个木料现在10米长,然后切的位置是2米处,4米处和7米处
(就是说arr A里A[0]是2,A[1]是4, A[2]是7)。那么比如先切2米,那么得到cost是
10(因为现在木料长度为10),然后切4米处,那么cost变成10 + 8(因为8是现在切的
时候木料的长度)。然后切7米处,cost变成10 + 8 + 6。那么这种切法总共的cost是24。

public int cutWood(int [] input, int L) {
        ArrayList a = new ArrayList();
        a.add(0);
        for (int i = 0; i < input.length; i++)
            a.add(input[i]);
        a.add(L);
        int [][] dp = new int [a.size()][a.size()];
        //initalize cut to 2 pieces
        for (int i = 1; i < a.size(); i++) { //i is the length of the log
            dp[1][i] = 0;
        }
        for (int i = 2; i < a.size(); i++) {
            for (int j = i; j < a.size(); j++) { // j is the ending point of the log
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = j - i + 1; k < j; k++) { // k is position we try to cut the log first into half, then look for the cost for the half(calculated previously
                    dp[i][j] = Math.min(dp[i][j], a.get(j) - a.get(j-i) + dp
[k - j + i][k] + dp[j - k][j]);
                }
            }
        }
        return dp[a.size()-1][a.size()-1];
       }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s