九章算法笔记D3-序列型动态规划

D3 序列型动态规划

Paint House II

题意：

有一排N栋房子，每栋房子要染成K种颜色中的一种，任何两栋相邻的房子不能染成同样的颜色。房子i染成第j种颜色的花费是cost[i][j] ，问最少需要花多少钱油漆这些房子

分析

转移方程 f[i][j]=min(k!=j){f[i-1][k]}+cost[i-1][j]

public int minCostII(int[][] C){
    int n = C.length;
    if(n==0)return 0;
    int K = C[0].length;
    int[][] f = new int[n+1][K];
    //minimum, second minimum
    int min1,min2;
    int id1=0,id2=0;
    //init
    for(i=0;i<K;i++){
        f[0][i]=0;
    }
    for(i=1;i<=n;i++){
        min1=min2=Integer.MAX_VALUE;
        for(j=0;j<K;j++){
            if(f[i-1][j]<min1){
                min2 = min1;
                id2 = id1;
                min1 = f[i-1][j];
                id1 = j;
            }else if(f[i-1][j]<min2){
                min2 = f[i-1][j];
                id2 = ;
            }
        }
        for(j=0;j<K;j++){
			f[i][j] = C[i-1][j];
            if(j!=id1)f[i][j]+=min1;
            else f[i][j]+=min2;
        }
    }
    int res = Integer.MAX_VALUE;
    for(i=0;i<K;i++){
        res = Math.min(res,f[n][i]);
    }        
    return res;
}

House Robber

题意：

有一排N栋房子（0~N-1），房子i里有A[i] 个金币，一个窃贼想选择一些房子偷金币，但是不能偷任何挨着的两家邻居，否则会被警察逮住，求最多偷多少金币

样例

Input
3 8 4
Output
8（只偷第二家的金币）

分析

设f[i]为窃贼在前 i 栋房子最多偷多少金币f[i] = max{ f[i-1],f[i-2]+A[i-1]}

初始条件：

1. f[0]=0（没有房子，偷0枚金币）
2. f[1]=A[0]只有一栋房子肯定偷

public long houseRoober(int[] A) {
        // use long
        int n = A.length;
        if (n == 0)
            return 0;
        if (n == 1)
            return A[0];
        long old = 0;// f[0]
        long now = A[0];// f[1]
        for (int i = 2; i <= n; i++) {
            // now = f[i-1]
            // old = f[i-2]
            long t = Math.max(now, old + A[i - 1]);// f[i]
            old = now;
            now = t;
        }
        return now;
    }

House RobberII

题目描述

有一圈 N栋房子（0~N-1），房子i里有A[i] 个金币，一个窃贼想选择一些房子偷金币，但是不能偷任何挨着的两家邻居，否则会被警察逮住，求最多偷多少金币

思路：

分情况考虑把环变成线

public int calc(int[] A){
    int n = A.length;
    if(n==0)return 0;
    if(n==1)return A[0];
    int old =0;
    int now = A[0];
    for(int i =2;i<=n;i++){
        int t = Math.max(now,old+A[i-1]);
        old = now;
        now = t;
    }
    return now;
}
public long houseRoober2(int[] nums) {
        // use long
        int n = nums.length;
        if (n == 0)
            return 0;
        if (n == 1)
            return nums[0];
        int[] A = new int[n-1];
    	int res = Integer.MIN_VALUE;
    	int i;
    for(i=0;i<n-1;i++){
        A[i]=nums[i];
    }
    res = Math.max(res,calc(A));
    for(i=0;i<n-1;i++){
        A[i] = nums[i+1];
    }
    res = Math.max(res,calc(A));
        return res;
    }

Best Time To Buy And Sell StockI

Problem：

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example

Given array [3,2,3,1,2], return 1.

public int maxProfit(int[] A) {
        int res = 0, mn = INT_MAX;
        for (int i = 0; i < A.length; ++i) {
            mn = Math.min(mn, A[i]);
            res = Math.max(res, A[i] - mn);
        }
        return res;
    }

Best Time To Buy And Sell StockII

Problem：

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times ). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example

Given an example [2,1,2,0,1], return 2

int maxProfit(vector<int> &prices) {
        int res = 0, n = prices.size();
        for (int i = 0; i < n - 1; ++i) {
            if (prices[i] < prices[i + 1]) {
                res += prices[i + 1] - prices[i];
            }
        }
        return res;
    }

Best Time To Buy And Sell StockIII

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

分析

思路： 不知道有没有买卖过，就记录下来

确定状态：

最优策略一定是前N天（第N-1天）结束后，处于

1. 阶段1：没买卖过（如果都是亏本生意就不做）
2. 阶段3：买卖过一次（赚过一次后都是亏本生意）
3. 阶段5：买卖过两次

子问题： f[i][j]表示前 i 天（第i-1天）结束后，在阶段j的最大获利

转移方程：f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + P[i - 1] - P[i - 2]);

public int maxProfit(int[] P) {
        int n = P.length;
        if (n == 0)
            return 0;
        int[][] f = new int[n + 1][5 + 1];
        int i, j;
        f[0][1] = 0;
        for (i = 2; i <= 5; i++) {
            f[0][i] = Integer.MIN_VALUE;
        }
        for (i = 1; i <= n; i++) {
            // 阶段1、3、5
            for (j = 1; j <= 5; j += 2) {
                f[i][j] = f[i - 1][j];
                if (j > 1 && i >= 2 && f[i - 1][j - 1] != Integer.MIN_VALUE) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + P[i - 1] - P[i - 2]);
                }
            }
            // 阶段2、4
            for (j = 2; j <= 5; j += 2) {
                f[i][j] = f[i - 1][j - 1];
                if (i >= 2 && f[i - 1][j] != Integer.MIN_VALUE) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j] + P[i - 1] - P[i - 2]);
                }
            }
        }
        return Math.max(f[n][1], Math.max(f[n][3], f[n][5]));
    }

Best Time To Buy And Sell StockIV

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Example

Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.

public int maxProfit(int K, int[] P) {
        int n = P.length;
        if (n == 0)
            return 0;
        int i, j;
        if (K > n / 2) {//如果K>N/2，题目可以简化为第二种类型  II
            int sum = 0;
            for (i = 0; i < n - 1; i++) {
                if (P[i + 1] > P[i]) {
                    sum += P[i + 1] - P[i];
                }
            }
            return sum;
        }
        // int[][] f = new int[n + 1][2 * K + 1];
        //使用滚动数组，所有i的改为now，i-1的为old
        int[][] f = new int[2][2 * K + 1];
        int old=0,now=0;

        f[now][1] = 0;
        for (i = 2; i <= 2 * K + 1; i++) {
            f[now][i] = Integer.MIN_VALUE;
        }
        for (i = 1; i <= n; i++) {
            // 阶段1、3、5、...、2*K + 1
            for (j = 1; j <= 2 * K + 1; j += 2) {
                f[now][j] = f[old][j];
                if (j > 1 && i >= 2 && f[old][j - 1] != Integer.MIN_VALUE) {
                    f[now][j] = Math.max(f[now][j], f[old][j - 1] + P[i - 1] - P[i - 2]);
                }
            }
            // 阶段2、4...2*K
            for (j = 2; j <= 2 * K; j += 2) {
                f[now][j] = f[old][j - 1];
                if (i >= 2 && f[old][j] != Integer.MIN_VALUE) {
                    f[now][j] = Math.max(f[now][j], f[old][j] + P[i - 1] - P[i - 2]);
                }
            }
        }
        int res = Integer.MIN_VALUE;
        for (i = 1; i <= 2 * K + 1; i++) {
            res = Math.max(res, f[now][i]);
        }
        return res;
    }

序列+状态型动态规划小结

1. 当思考动态规划最后一步时，这一步的选择依赖于前一步的某种状态
2. 初始化时，f[0]代表前0个元素/前0天的情况（与坐标型动态规划区别）
3. 计算式，f[i]代表前i个元素（即元素0~i-1）的某种性质

Russian Doll Envelopes

Problem:

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:

Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

public int maxEnvelopes(int[][] A){//此处为O（N*N）不能Accpect
        if(A==null||A.length==0)return 0;
    	//先给数组排序
        Arrays.sort(A,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                //长度
                if(a[0]==b[0]){
                    return a[1]-b[1];
                }else{
                    return a[0]-b[0];
                }
            }
        });

        int n = A.length;
        int[] f = new int[n];
        int i,j,res=0;
        for(i=0;i<n;i++){
            //初始化
            f[i]=1;
            //枚举第二外的信封
            for(j=0;j<i;j++){
                //如果这个的长宽都比小，则可以塞进去，就进行比较
                if(A[j][0]<A[i][0]&&A[j][1]<A[i][0]){
                    //虽然上面已经按长度排序，但长度可能相等，所以需要再次进行比较
                    f[i] = Math.max(f[i],f[j]+1);
                }
            }
            res = Math.max(res,f[i]);
        }
        return res;
    }

---