彩票平台:首页 > 学习之路 > ACM||算法ACM||算法

113彩票官网 | 序列+状态型113彩票官网

卞振伟2019-02-27【ACM||算法】人已围观

简介113彩票官网(简称DP)是算法设计思想当中最难也是最有趣的部分了,113彩票官网适用于有重叠子问题和最优子结构性质的问题,是一种在数学、计算机科学和经济学中经常使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。使用113彩票官网方法解题有较高的时间效率,关键在于它减少了很多不必要的计算和重复计算的部分

当思考113彩票官网最后一步时,这一步的选择依赖于前一步的某种状态                                                                                     

注册登录:

    Paint House      房屋染色  房屋染色Ⅱ                                             
                                                                                                          
    House Robber   打劫房屋  打劫房屋Ⅱ
    这个题有更好的解法,我就不用序列+状态了。用序列+状态型很简单,聪明的你一定可以实现

    Best Time to Buy and Sell Stock Ⅲ || Ⅳ   买卖股票的最佳时机Ⅲ  买卖股票的最佳时机 Ⅳ
    买卖股票的最佳时机Ⅰ   买卖股票的最佳时机 Ⅱ
    买卖股票的最佳时机 Ⅲ 与 Ⅳ 典型序列+状态型113彩票官网

 


 

彩票开奖. 房屋染色

这里有n个房子在一列直线上,现在我们需要给房屋染色,分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小,返回最小的费用。

费用通过一个nx3 的矩阵给出,比如cost[0][0]表示房屋0染红色的费用,cost[1][2]表示房屋1染绿色的费用。

彩票开奖结果

彩票开奖结果 1:

输入: [[14,2,11],[11,14,5],[14,3,10]]
输出: 10
解释: 蓝 绿 蓝, 2 + 5 + 3 = 10

彩票开奖结果 2:

输入: [[1,2,3],[1,4,6]]
输出: 3

开奖记录查询

所有费用都是正整数

public class Solution {
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
        // write your code here
        if(costs == null || costs.length == 0)
            return 0;
            
        int n = costs.length;
        int[][] dp = new int[n+1][3];
        dp[0][0] = dp[0][1] = dp[0][2] = 0;
        
        for (int i = 1; i <= n; ++i){
            for (int j = 0; j < 3; ++j){
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; ++k){
                    if(j != k){
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + costs[i-1][j]);
                    }
                }
            }
        }
        
        int ans = dp[n][0];
        ans = Math.min(ans, dp[n][1]);
        ans = Math.min(ans, dp[n][2]);
        return ans;
    }
}
 

516. 房屋染色 II

这里有n个房子在一列直线上,现在我们需要给房屋染色,共有k种颜色。每个房屋染不同的颜色费用也不同,你需要设计一种染色方案使得相邻的房屋颜色不同,并且费用最小。

费用通过一个nxk 的矩阵给出,比如cost[0][0]表示房屋0染颜色0的费用,cost[1][2]表示房屋1染颜色2的费用。

彩票开奖结果

costs = [[14,2,11],[11,14,5],[14,3,10]] return 10

房屋 0 颜色 1, 房屋 1 颜色 2, 房屋 2 颜色 1, 2 + 5 + 3 = 10

挑战

用O(nk)的时间复杂度解决

开奖记录查询

所有费用都是正整数

public class Solution {
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        // write your code here
        if(costs == null || costs.length == 0 || costs[0].length == 0)
            return 0;
        
        int n = costs.length;
        int m = costs[0].length;
        int[][] dp = new int[n+1][m];
        
        for(int i = 0; i < m; ++i)
            dp[0][i] = 0;
        
        for(int i = 1; i <= n; ++i){
            for(int j = 0; j < m; ++j){
                dp[i][j] = Integer.MAX_VALUE;
                for(int k = 0; k < m; ++k){
                    if(j != k)
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + costs[i-1][j]);
                }
            }
        }
        
        int ans = dp[n][0];
        for(int i = 1; i < m; ++i)
            ans = Integer.min(ans, dp[n][i]);
        
        return ans;
    }
}

392. 打劫房屋

假设你是一个专业的窃贼,准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警

给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,在不触动报警装置的情况下, 你最多可以得到多少钱 。

彩票开奖结果

彩票开奖结果 1:

输入: [3, 8, 4]
输出: 8
解释: 仅仅打劫第二个房子.

彩票开奖结果 2:

输入: [5, 2, 1, 3] 
输出: 8
解释: 抢第一个和最后一个房子

挑战

O(n) 时间复杂度 且 O(1) 存储。//若要实现O(1)的存储,只需把数组改为两个变量即可。
 

public class Solution {//序列型113彩票官网,先做个简单的过渡一下
    /**
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    public long houseRobber(int[] A) {
        // write your code here
        int n = A.length;
        if(n == 0)
            return 0;
        
        long[] dp = new long[n+1];
        
        dp[0] = 0;
        dp[1] = A[0];
        
        for(int i = 2; i <= n; ++i){
            dp[i] = Math.max(dp[i-1], dp[i-2] + A[i-1]);
        }
        
        return dp[n];
    }
}


public class Solution { //O(n) 时间复杂度 且 O(1) 存储。 若要实现O(1)的存储,只需把数组改为三个变量即可。
    /**
     * @param A: An array of non-negative integers
     * @return: The maximum amount of money you can rob tonight
     */
    public long houseRobber(int[] A) {
        // write your code here
        int n = A.length;
        if(n == 0)
            return 0;
        
        long[] dp = new long[3];
        
        dp[0] = 0;
        dp[1] = A[0];
        int k = 2;
        
        for(int i = 2; i <= n; ++i){
            dp[i%3] = Math.max(dp[(i-1)%3], dp[(i-2)%3] + A[i-1]);
        }
        
        return dp[n%3];
    }
}


534. 打劫房屋 II

在上次打劫完一条街道之后,窃贼又发现了一个新的可以打劫的地方,但这次所有的房子围成了一个圈,这就意味着第一间房子和最后一间房子是挨着的。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警

给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,在不触动报警装置的情况下, 你最多可以得到多少钱 。

彩票开奖结果

彩票开奖结果1

输入: nums = [3,6,4]
输出: 6

彩票开奖结果2

输入: nums = [2,3,2,3]
输出: 6

开奖记录查询

这题是House Robber的扩展,只不过是由直线变成了圈

/**仅对最后一所房子进行讨论,

如果不打劫,和前一篇文章一样,此时结果为dp[(n-1)%3];

如果打劫,则意味着第一所房子不能打劫,即dp[1] = 0 dp[2] = nums[1],这样重来一次113彩票官网,此时的结果为 dp[n%3];
*/
public class Solution {
    /**
     * @param nums: An array of non-negative integers.
     * @return: The maximum amount of money you can rob tonight
     */
    public int houseRobber2(int[] nums) {
       // write your code here
        int n = nums.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        if(n == 2)
            return Math.max(nums[0],nums[1]);
        
        int[] dp = new int[3];
        
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= n-1; ++i)
            dp[i%3] = Math.max(dp[(i-1)%3], dp[(i-2)%3] + nums[i-1]);
            
        int ans = dp[(n-1)%3];
        
        dp[1] = 0;
        dp[2] = nums[1];
        for(int i = 3; i <= n; ++i)
            dp[i%3] = Math.max(dp[(i-1)%3], dp[(i-2)%3] + nums[i-1]);
        ans = Math.max(ans, dp[n%3]);
        
        return ans;
    }
}
 

151. 买卖股票的最佳时机 III

假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

Example

给出一个彩票开奖结果数组 [4,4,6,1,1,4,2,5], 返回 6

Notice

你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        int n = prices.length;
        if(n == 0)
            return 0;
            
        //阶段1:第一次买之前
        //阶段2:持有股票
        //阶段3:第一次卖之后,第二次买之前
        //阶段4:持有股票
        //阶段5:第二次卖之后
        
        int[][] dp = new int[n+1][5+1];
        dp[0][1] = 0;
        for(int i = 2; i < 6; ++i)
            dp[0][i] = Integer.MIN_VALUE;

        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= 5; j+=2){//1  3  5
                dp[i][j] = dp[i-1][j];
                if(j > 1 && i > 1 && dp[i-1][j-1] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + prices[i-1] - prices[i-2]);
                if(j > 2 && i > 1 && dp[i-1][j-2] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-2] + prices[i-1] - prices[i-2]);
            }
            for(int j = 2; j <= 5; j+=2){//2  4
                dp[i][j] = dp[i-1][j-1];//买这股股票变为2  4状态
                if(i > 1 && dp[i-1][j] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + prices[i-1] - prices[i-2]);
                if(j > 2 && i > 1 && dp[i-1][j-2] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-2] + prices[i-1] - prices[i-2]);
            }
        }
        return Math.max(Math.max(dp[n][1], dp[n][3]), dp[n][5]);
    }
}
 

393. 买卖股票的最佳时机 IV

假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。

设计一个算法来找到最大的利润。你最多可以完成 k 笔交易。

Example

给定价格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.

Challenge

O(nk) 时间序列。

Notice

你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

public class Solution {
    /**
     * @param K: An integer
     * @param prices: An integer array
     * @return: Maximum profit
     */
    public int maxProfit(int K, int[] prices) {
        // write your code here
        int n = prices.length;
        if(n == 0)
            return 0;
        int ans = 0;
        if(K >= n/2){
            for(int i = 1; i < n; ++i)
                ans += Math.max(prices[i] - prices[i-1], 0);
            return ans;
        }

        int[][] dp = new int[n+1][2*K+1 + 1];
        dp[0][1] = 0;
        for(int i = 2; i <= 2*K+1; ++i)
            dp[0][i] = Integer.MIN_VALUE;
        
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= 2*K+1; j += 2){
                dp[i][j] = dp[i-1][j];
                if(i > 1 && j > 1 && dp[i-1][j-1] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + prices[i-1] - prices[i-2]);
                // if(i > 1 && j > 2 && dp[i-1][j-2] != Integer.MIN_VALUE)
                //     dp[i][j] = Math.max(dp[i][j], dp[i-1][j-2] + prices[i-1] - prices[i-2]);
            }
            for(int j = 2; j <= 2*K+1; j += 2){
                dp[i][j] = dp[i-1][j-1];
                if(i > 1 && dp[i-1][j] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + prices[i-1] - prices[i-2]);
                if(i > 1 && j > 2 && dp[i-1][j-2] != Integer.MIN_VALUE)
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-2] + prices[i-1] - prices[i-2]);
            }
        }
        ans = Integer.MIN_VALUE;
        for(int i = 1; i <= 2*K+1; i+=2)
            ans = Math.max(ans, dp[n][i]);
        return ans;
    }
}


149. 买卖股票的最佳时机

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

Example

给出一个数组彩票开奖结果 [3,2,3,1,2], 返回 1 
 

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        int n = prices.length;
        if(n == 0)
            return 0;
        int Min = prices[0];
        int ans = 0;
        for(int i = 1; i < n; ++i){
            if(Min > prices[i])
                Min = prices[i];
            ans = Math.max(ans, prices[i] - Min);
        }
        return ans;
    }
}

150. 买卖股票的最佳时机 II

假设有一个数组,它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。

Example

给出一个数组彩票开奖结果[2,1,2,0,1], 返回 2

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        int n = prices.length;
        if(n == 0)
            return 0;
        
        int ans = 0;
        for(int i = 1; i < n; ++i){
            if(prices[i] > prices[i-1])
                ans += prices[i] - prices[i-1];
        }
        return ans;
    }
}

 

Tags:ACM   编程   个人   题解   算法   C|C++   java

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:71篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00