DP

动态规划 (Dynamic Programing) 是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

# 标题 奖励 解出人数
5734 孤星 4.6 x 206
5201 Kaleidoscope 3.6 x 109
5200
DP
Bare Minimum Difference
3.6 x 144
5169 地球签证 4.0 x 66
5158
DP
排头兵
6.2 x 16
5068
DP
CHAO!OP!
2.8 x 126
5044
DP
宝箱
4.7 x 183
5042 龟速飞行棋 7.0 x 25
5041 套娃 5.8 x 62
4253 力脑 9.9 x 1
3653 她的名字 3.8 x 255
3647 小猪分类 8.2 x 7
3568
DP
棋盘染色
9.2 x 4
3563
DP
校园卡清零
6.2 x 39
3544
DP
小迷妹在哪儿
3.3 x 227
3543
DP
夜游 ECNU
4.7 x 50
3531
DP
定西
0.9 x 2164
3489 坑爹的售票机 4.5 x 158
3483 最小 OR 路径 (EASY) 4.9 x 66
3479
DP
现任总统的巡游
6.9 x 11
3470
DP
Zoltan
9.7 x 2
3447
DP
比昨天更多的棒棒糖 (Hard)
5.0 x 30
3438
DP
棋盘上的車
7.3 x 7
3437
DP
卡车运输
6.2 x 9
3432
DP
Smooth Array
8.6 x 3
3395 铺瓷砖问题 9.0 x 4
3373 骑士游戏 6.0 x 9
3367 咸鱼翻身 2.6 x 208
3365 打字员吉吉木 6.8 x 11
3354 领外卖 3.2 x 206
3338
DP
双塔问题
3.0 x 232
3330 沉陷过往的幻灭 5.6 x 12
3329
DP
奇异收缩的剪影
4.5 x 26
3297 铺瓷砖 1.2 x 564
3267
DP
足球锦标赛
2.2 x 408
3261 分词 3.8 x 111
3257 七减一 4.5 x 119
3253
DP
玉米和葡萄
4.1 x 80
3239
DP
最长的等差数列
1.0 x 787
3227 声控开关 (Hard) 2.8 x 94
3226 声控开关 (Easy) 2.7 x 112
3092 GDP 0.9 x 444
3072
DP
小巴菲特买股票
0.9 x 566
3051 台阶走法数 0.9 x 1200
3034 数字拆分 1.3 x 778
3029 不重复正整数 0.1 x 812
3010
DP
Coins (III)
4.0 x 40
3009
DP
Coins (II)
3.0 x 49
3008
DP
Coins (I)
3.4 x 78
3005 小型组合数 1.3 x 1145
2999
DP
计算多项式的系数
1.1 x 1186
2958
DP
求上升子序列和的最大值
0.5 x 1007
2922 Minimizing maximizer 7.1 x 8
2921
DP
Corn Fields
6.6 x 10
2920 Mondriaan's Dream 4.7 x 23
2857
DP
编辑距离
1.1 x 916
2854 统计特定字串模式的个数 0.3 x 1334
2846 统计字符串个数 0.3 x 1684
2799
DP
区间覆盖
2.5 x 191
2798 斐波那契数列和 2.5 x 232
2777 Moving to Nuremberg 6.6 x 10
2743
DP
Stock Exchange
4.2 x 36
2726
DP
Recursively Palindromic Partitions
4.8 x 14
2686 Matchsticks 4.8 x 27
2585
DP
0-1 Package
3.0 x 150
2441
DP
Legendary Brave, TOKOSHI
5.9 x 13
2307
DP
Pirates’ Gold
7.1 x 11
2245 DNA Laboratory 9.9 x 1
2233
DP
Strange Towers of Hanoi
3.9 x 15
2212
DP
Lecture halls reservation
7.8 x 6
2211 The number of n-k-special sets 7.9 x 5
2168 Game Dice 7.7 x 7
2146
DP
奥运队形
8.6 x 5
2103
DP
小强寻宝I
7.2 x 11
2083
DP
ZigZag
2.0 x 222
2075
DP
汉堡大赛
7.0 x 9
2074
DP
Ant Counting
5.2 x 12
2064
DP
Bookshelf 2
3.5 x 58
2042
DP
Eating Together
4.6 x 26
1976
DP
Common Subsequence
4.9 x 24
1843 津津骑马 3.3 x 171
1825
DP
数塔IV
2.9 x 151
1824
DP
数塔III
1.9 x 386
1823
DP
数塔II
3.5 x 184
1805 最长连续公共子序列 2.8 x 775
1536
DP
Ugly Numbers
3.7 x 73
1516
DP
Unidirectional TSP
7.2 x 9
1494
DP
Coins
3.9 x 46
1279
DP
Compromise
6.4 x 13
1271 The Tower of Babylon 5.3 x 24
1255
DP
Brackets sequence
4.4 x 20
1244
DP
积木游戏
3.9 x 65
1238 加分二叉树 4.2 x 82
1237
DP
合唱队形
3.7 x 59
1226
DP
Stones Game
3.6 x 49
1203
DP
Piggy-Bank
5.1 x 24
1186 Anniversary party 3.3 x 32
1163 easy to do DP 2.8 x 258
1129 考新郎 4.7 x 166
1113
DP
装箱问题
1.8 x 629
标签云