博客首页 → 动态规划

最新文章列表

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 爬楼梯的问题，思路和Unique Paths问题类似。我们假设到了 ...
动态规划java 
KickCode 评论(0) 有529人浏览 2016-02-02 02:13

Unique Paths II

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in t ...
动态规划java 
KickCode 评论(0) 有668人浏览 2016-02-01 05:57

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bot ...
动态规划java 
KickCode 评论(0) 有602人浏览 2016-02-01 05:25

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has th ...
java动态规划 
KickCode 评论(0) 有418人浏览 2016-01-30 14:19

Wildcard Matching 通配符

Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover th ...
动态规划 
KickCode 评论(0) 有1139人浏览 2016-01-29 02:45

Range Sum Query 2D - Immutable

Given a 2D matrix matrix[][], find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). Example: Given matrix = [   [3, 0, 1, ...
java动态规划树状数组 
KickCode 评论(0) 有861人浏览 2016-01-22 15:56

Coin Change

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 amoun ...
java动态规划 
KickCode 评论(0) 有752人浏览 2016-01-10 06:03

Wildcard Matching

Wildcard Matching 给定两个字符串p和q，判断两个字符串是否匹配。规则是：‘*’可以代表任意长度的字符串，也可以代表空串；‘?’代表任意单个的字符串。 例如： isMatch("aa", "a") → false isMatch("aa", "aa") → true isMatch("aaa&q ...
java动态规划wildcard matching 
KickCode 评论(0) 有354人浏览 2015-12-24 01:36

动态规划总结(三)

House Robber问题属于一维的动规问题，这篇文章给大家介绍一下。 1，House Robber 一个小偷去一条街上偷东西，假设这条街上有n个房子，每个房子里都有特定的现金，但是小偷不能偷连续的房子，那样会触发警报，问怎样才能偷到最多的钱。 我们把这条街抽象成一个数组，数组里的值代表了房子里现金的数目，假设小偷拿了第0个房子的钱，那么第1个房子的钱就不能拿，否则就会触发警报。我们创建一个数 ...
java动态规划 
KickCode 评论(0) 有978人浏览 2015-12-22 07:52

动态规划总结(二)

这篇文章介绍unique path等一系列的题目，它们属于二维动态规划的问题，之前一篇文章讲过最长公共子序列(LCS), 最长递增子序列(LIS), 最长非降子序列。有兴趣的可以看一下，这些都是经典的二维动规问题。 1，Unique Paths 给定一个m*n的矩阵，一个机器人在这个矩阵的左上方，它试图走到这个矩阵的右下方，规定机器人只能往右和往下两个方向走，问有多少种不同的路径。 我们把这个矩 ...
javaunique path动态规划 
KickCode 评论(0) 有614人浏览 2015-12-21 02:32

动态规划总结(一)

动态规划在算法中属于难的问题了，在leetcode中属于中等偏上难度，但是动规是面试容易问到的，因此掌握基本的动规题目很有必要。下面列举leetcode中用DP处理的题目，其中有些用到贪心算法，就不单列出来了，本质上贪心也是动态规划的一个特例。动态规划重要的是能找出递推式，这需要我们多加练习，需要有一个过程。 有关买卖股票的题目有几道，这里列举前两道题。 1，Best Time to Buy an ...
java动态规划 
KickCode 评论(0) 有802人浏览 2015-12-20 13:37

时间序列分段算法 [Time series Breakout Detection]

在时间序列分析中，断点检测（breakout detection）是一个很基本的问题。 通过捕捉时序数据中的断点（breakout），来发现时序数据所表示的系统在过去是否发生了某种事件（event）,进而为系统诊断提供必要的数据支持。   为了实现对时序断点的检测，我们首先需要对时序的整体时序做拟合。 这里我们通过一条直线来拟合一段时序，如果时序的趋势发生了变化，则用多条直线来拟合整条时 ...
时间序列动态规划线性回归断点检测BreakoutDetection 
liuzhiqiangruc 评论(0) 有6425人浏览 2015-12-15 20:01

LeetCode[动态规划] - #5 Longest Palindromic Substring

原题链接：#5 Longest Palindromic SubString   要求： 给定一个字符串S，找出它的最长回文子串。假定S的最大长度为1000，且最长回文子串唯一   难度：中等   分析： 假定字符串s为回文字符串，则在s头部和尾部分别添加相同字符串[x]，所得结果s'=[x]s[x]也为回文字符串（论述1）。可使用动态规划方法解决此问题，递推公式便基于此特性。 创 ...
LeetCodeJavaAlgorithm题解动态规划 
Cwind 评论(3) 有5433人浏览 2015-08-04 22:52

LeetCode[动态规划] - #198 House Robber

原题链接：#198 House Robber   要求： 原题是要为某盗贼设计一个能使其利益最大化的方案（这个场景并不和谐，在保持题意的情况下重新描述一个场景）。假设某糖果工厂有若干糖果机，每台糖果机每天产出不同数量的糖果，每天取糖果时不能同时取相邻两台糖果机的糖果（别问为什么），问每天能取得的最大糖果数量是多少。   糖果机产生的糖果数量集合可以看成一个整型数组。   难度：简单 ...
LeetCodeJavaAlgorithm题解动态规划 
Cwind 评论(0) 有3230人浏览 2015-08-03 15:17

动态规划算法学习

给定待粉刷的n个墙砖(排成一行)，每个墙砖可以粉刷的颜色种类为:红、蓝、绿、黄，问粉刷完毕后，红色墙砖和蓝色墙砖都是偶数的粉刷方式有多少种( ...
java算法动态规划粉刷algorithm 
Vitas_Wang 评论(0) 有609人浏览 2015-07-28 22:40

LeetCode[动态规划] - #10 Regular Expression Matching

原题链接：#10 Regular Expression Matching   要求： 实现正则表达式匹配，支持'.'和'*'。   '.'匹配任意单字符。 '*'匹配任何0个或多个之前元素。   匹 ...
LeetCodeJavaAlgorithm题解动态规划 
Cwind 评论(0) 有6495人浏览 2015-07-20 12:25

LeetCode[动态规划] - #7 Climbing Stairs

原题链接：#7 Climbing Stairs   问题： 你正在攀爬一把一共有n个台阶的梯子，每次可以爬一或二阶，爬到顶共有多少种不同的方式？   难度：简单   分析： 当梯子阶数为0时，有0种攀爬方式；当阶数为1时，则有一种攀爬方式。当阶数为2时，由于每次可以爬一阶或两阶，即从0阶处爬两阶到达顶部或由1阶处爬1阶到达顶处，共2种方式。n=3时同样，可以由1阶处爬两阶或由2阶处 ...
LeetCodeJavaAlgorithm题解动态规划 
Cwind 评论(0) 有2163人浏览 2015-07-19 23:03

188 Best Time to Buy and Sell Stock IV——leetcode

  class Solution { public: Solution(){} int maxProfit(int K, vector<int> &prices) { vector<int> lowVec; vector<int > highVec; if(prices ...
动态规划leetcode 
lvdccyb 评论(0) 有946人浏览 2015-04-11 20:29

Viterbi 算法应用实现

算法简介： Viterbi 算法又叫维特比算法，其是HMM模型中在给出观测序列O，以及状态转移举证M 和 状态-观测矩阵Q之后，求解能够最佳解释序列O的状态序 ...
数据挖掘算法C动态规划序列平滑 
liuzhiqiangruc 评论(2) 有7412人浏览 2014-12-22 10:51

最近博客热门TAG

Java(141747) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54918) .net(54785) Web(54513) 工作(54116) Linux(50906) Oracle(49876) 应用服务器(43288) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37268) 数据结构(36423)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics