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

113彩票官网 | 缘起

卞振伟2019-01-24【ACM||算法】人已围观

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

什么是113彩票官网(附链接)

 

缘起:

 
113彩票官网把原问题分解为相对简单的子问题的方法一直困惑着我,虽然在不断学习,终究没能学通。认真反思一下自己,113彩票官网就背包问题做的比较好罢了。故最终下定决定,学通113彩票官网。。。


113彩票官网题目特点


     <1> 计数
         -有多少种方式走到右下角
         -有多少种方式选出k个数使得和是Sum
         
     <2>求最大最小值
         -从左上角走到右下角路径的最大数字和
         -最长上升子序列长度
         
     <3>求存在性
         -取石子游戏,先手是否必胜
         -能不能选出k个数使得和是Sum


简单入手:

LintCode 114:Unique Paths [计数型113彩票官网]

114. Unique Paths

A robot is located at the top-left corner of a m x n grid.

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

How many possible unique paths are there?

Example

Given m = 3 and n = 3, return 6.
Given m = 4 and n = 5, return 35.

Notice

m and n will be at most 100.

 
public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int uniquePaths(int m, int n) {
        // write your code here
        int[][] arr=new int[m][n];
        // int [n-1][n-1]=f[n-2][n-1]+f[n-1][n-2];
        for(int i=0;i<n;i++)
            arr[0][i]=1;
        for(int i=0;i<m;i++)
            arr[i][0]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                arr[i][j]=arr[i-1][j]+arr[i][j-1];
            }
        }
        return arr[m-1][n-1];
    
}

LintCode 669:Coin Change [最值型113彩票官网]
 

669. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example

Given coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Given coins = [2], amount = 3
return -1.

Notice

You may assume that you have an infinite number of each kind of coin.

public class Solution {
    /**
     * @param coins: a list of integer
     * @param amount: a total amount of money amount
     * @return: the fewest number of coins that you need to make up
     */
    public int coinChange(int[] coins, int amount) {
        // write your code here
        int n = amount;
        int[] f = new int[amount + 1];
        f[0] = 0;
        
        int i, j;
        
        for (i = 1; i <= n; ++i) {
            f[i] = Integer.MAX_VALUE;
            for (j = 0; j < coins.length; ++j) {
                if (i >= coins[j] && f[i - coins[j]] != Integer.MAX_VALUE )
                    f[i] = Math.min(f[i] , f[i - coins[j]] + 1);
            }
        }
        if (f[i - 1] == Integer.MAX_VALUE)
            return -1;
        return f[i - 1];
    }
}

LintCode 116:Jump Game[存在型113彩票官网]

116. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Notice

This problem have two method which is Greedy and Dynamic Programming.

The time complexity of Greedy method is O(n).

The time complexity of Dynamic Programming method is O(n^2).

We manually set the small data set to allow you pass the test in both ways. This is just to let you learn how to use this problem in dynamic programming ways. If you finish it in dynamic programming ways, you can try greedy method to make it accept again.

 
public class Solution {
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    public boolean canJump(int[] A) {
        // write your code here
        int n = A.length;
        boolean[] f = new boolean[n];
        f[0] = true;
        
        for (int i = 1; i < n; ++i) {
            f[i] = false;
            for (int j = 0; j < i; ++j) {
                if (f[j] && j + A[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n - 1];
    }
}

 

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

很赞哦! ()

文章评论

站点信息

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

客服在线

QQ客服

客服微信扫码

服务时间

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