博客首页 → Dynamic Programming

最新文章列表

Leetcode - 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? [分析] 一维动态规划入门题   public ...
Dynamic Programming 
likesky3 评论(1) 有823人浏览 2015-04-10 10:04

Leetcode - Unique Binary Search Trees

[题目] Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BST's.   [分析] n个节点的BST的结构数等于从1到n依次为root节点对应的 ...
Dynamic Programming 
likesky3 评论(2) 有568人浏览 2015-04-10 10:00

Leetcode - Maximum Product Subarray

[题目] Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4],the contiguous subarray [2,3] has the larges ...
Dynamic Programming 
likesky3 评论(1) 有556人浏览 2015-04-10 09:52

Leetcode - House Robber

[题目] You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent ...
dynamic programming 
likesky3 评论(4) 有948人浏览 2015-04-01 09:06

Least Jumps of Frog Cross River

Question: 跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石头上。问最少几步可以跳完整条河流。给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：第一步先提速到2，再跳到R[2]；第二步先提速到3，再跳到R[5]；第三步保持速度3，跳出数组范围，成功过河。 ...
dynamic programmingleapfrog青蛙过河 
yuanhsh 评论(0) 有1070人浏览 2015-01-09 11:40

LeetCode - Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.For example, given s = "aab", R ...
leetcodedynamic programmingPalindrome Partitioning II 
yuanhsh 评论(0) 有756人浏览 2015-01-05 14:15

Dynamic Programming - Integer Knapsack

Reference: https://web.cs.ship.edu/~tbriggs/dynamic/ The Integer Knapsack problem is a famous rubrick in Computer Science. The problem has a simple brute-force solution. However, solving large ins ...
dynamic programminginteger knapsack 
yuanhsh 评论(0) 有1294人浏览 2015-01-04 13:53

A Greedy Knapsack Heuristic

1.  Strategies for NP-Complete Problems     --  Identify computationally tractable special cases.         - knapsack capacity W = polynomial in number of items n     --  Heuristics         - Pret ...
Approximation AlgorithmNP-CompleteKnapsack ProblemHeuristicDynamic Programming 
leonzhx 评论(0) 有1124人浏览 2013-10-30 15:41

Exact Algorithms for NP-Complete Problems

1.  The Vertex Cover Problem     --  Input: An undirected graph G = (V , E).     --  Goal: Compute a minimum-cardinality vertex cover -- a subset S subset of V that contains at least one endpoint o ...
Travelling Salesman ProblemTSPExact ApproachDynamic ProgrammingVertex Cover Problem 
leonzhx 评论(0) 有1139人浏览 2013-10-15 19:23

Optimal Binary Search Trees

1.  Problem Denition     --  Input: Frequencies p1, p2, ... , pn for items 1, 2, ... , n. [Assume items in sorted order, 1 < 2 < ... < n]     --  Goal: Compute a valid search tree that min ...
Optimal Binary Search TreeDynamic ProgrammingDynamic Planning 
leonzhx 评论(0) 有1036人浏览 2013-10-05 00:44

Sequence Alignment

1.  Problem Definition:     a)  Input: Strings X = x1 ... xm, Y = y1 ... yn over some alphabet Sigma (like {A,C,G,T})     b)  Penalty Pgap for inserting a gap, Pab for matching a & b [presumably ...
Sequence AlignmentEditor DistanceDynamic ProgrammingNeedleman-Wunsch ScoreDynamic Planning 
leonzhx 评论(0) 有1019人浏览 2013-10-04 22:29

The Knapsack Problem

1.  Problem Denition     --  Input: n items. Each has a:         a) Value vi (nonnegative)         b) Size wi (nonnegative and integral)         Capacity W (a nonnegative integer)     --  Output ...
The Knapsack ProblemDynamic ProgrammingDynamic Planning 
leonzhx 评论(0) 有950人浏览 2013-10-04 20:09

Introduction to Dynamic Programming and Weighed Independent Set in Graph

1.  Problem Definition of WIS in Graph:     --  Input: A path graph G = (V , E) with nonnegative weights on vertices.     --  Output: Subset of nonadjacent vertices (an independent set ) of maximum ...
Dynamic ProgrammingDynamic PlanningWeighed Independent Set 
leonzhx 评论(0) 有1495人浏览 2013-10-04 19:46

动态规划（dynamic programming）

方法概述: 发展及研究内容 动态规划(dynamic programming)是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—— ...
动态规划算法dynamic programming 
静妙仙人 评论(0) 有3473人浏览 2012-10-10 12:57

hdu 4354 Missile

被坑了！！10^9 - (-10^9) 会超过 0x3f3f3f3f , 搞的我 2 2 2 0 999999999 1 -999999999 2 这组直接输出 - 1  #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<q ...
Dynamic Programming 
dayandn 评论(0) 有20人浏览 2012-08-13 20:04

light oj 1128 倍增法LCA + DP

题意：一棵树，每个点都有一个点权，给你q个询问a b，求a到根节点的路径中点权大于等于b且最接近根节点的点编号 刚开始想用树链剖分搞，后来听说用倍增+DP也行 做法： 如果懂倍增法求祖先的方法的话，那么这个DP就能很快理解了，详情见代码 dp[i][j]表示i到i的2^j祖先的路径上的点权的最大值 那么在找的时候只需要log(n)的复杂度就可以找到最上面的点权大于等于b的啦 ...
Dynamic Programming 
yujing_yu 评论(0) 有6人浏览 2012-08-11 23:17

最近博客热门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