DP

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

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

# 标题 奖励 解出人数
3653
DP
她的名字
6.6 x 152
3647 小猪分类 9.2 x 7
3568
DP
棋盘染色
9.7 x 2
3563
DP
校园卡清零
6.6 x 27
3544 小迷妹在哪儿 6.8 x 121
3543 夜游 ECNU 7.8 x 37
3531
DP
定西
5.7 x 415
3507
DP
坑爹的售票机 (Easy)
5.9 x 326
3489 坑爹的售票机 4.7 x 100
3483 最小 OR 路径 (EASY) 5.1 x 49
3479
DP
现任总统的巡游
6.5 x 11
3470
DP
Zoltan
9.9 x 1
3447
DP
比昨天更多的棒棒糖 (Hard)
4.9 x 25
3446 骰子点数之和问题 7.2 x 78
3438
DP
棋盘上的車
6.0 x 7
3437
DP
卡车运输
5.7 x 8
3432
DP
Smooth Array
8.9 x 1
3395
DP
铺瓷砖问题
9.4 x 2
3373 骑士游戏 6.3 x 5
3365 打字员吉吉木 6.8 x 7
3355 开心消消乐 6.4 x 21
3354 领外卖 6.9 x 107
3338
DP
双塔问题
4.9 x 52
3330 沉陷过往的幻灭 5.2 x 9
3329
DP
奇异收缩的剪影
4.2 x 21
3302
DP
打印
6.5 x 162
3297 铺瓷砖 6.7 x 128
3281
DP
找不到路哒 ultmaster
4.1 x 59
3267
DP
足球锦标赛
6.0 x 312
3261 分词 4.0 x 94
3257
DP
七减一
7.4 x 63
3133 最长回文子串 1.8 x 200
3051 台阶走法数 4.0 x 155
3034
DP
数字拆分
2.5 x 170
3029
DP
不重复正整数
6.5 x 171
3010
DP
Coins (III)
4.0 x 28
3009
DP
Coins (II)
2.7 x 32
3008
DP
Coins (I)
3.8 x 44
3005 小型组合数 5.6 x 474
2999 计算多项式的系数 2.3 x 377
2958
DP
求上升子序列和的最大值
1.6 x 382
2922 Minimizing maximizer 7.7 x 5
2921
DP
Corn Fields
8.5 x 4
2920
DP
Mondriaan's Dream
6.0 x 11
2912 放书 6.5 x 168
2857
DP
编辑距离
6.2 x 254
2854
DP
统计特定字串模式的个数
6.0 x 311
2799
DP
区间覆盖
4.9 x 11
2798 斐波那契数列和 7.7 x 41
2743
DP
Stock Exchange
7.9 x 32
2726
DP
Recursively Palindromic Partitions
4.9 x 11
2686 Matchsticks 4.7 x 24
2585
DP
0-1 Package
3.6 x 98
2527
DP
Fj & haozi
2.2 x 386
2441
DP
Legendary Brave, TOKOSHI
8.9 x 10
2307
DP
Pirates’ Gold
7.2 x 10
2245 DNA Laboratory 9.9
2233
DP
Strange Towers of Hanoi
4.1 x 12
2212
DP
Lecture halls reservation
8.5 x 4
2211
DP
The number of n-k-special sets
7.7 x 4
2168 Game Dice 8.8 x 4
2083
DP
ZigZag
2.3 x 174
2074
DP
Ant Counting
6.0 x 9
2064
DP
Bookshelf 2
7.5 x 51
2042
DP
Eating Together
4.8 x 24
1976
DP
Common Subsequence
5.1 x 19
1843 津津骑马 7.2 x 73
1825
DP
数塔IV
7.3 x 66
1824
DP
数塔III
2.3 x 195
1823
DP
数塔II
6.8 x 122
1805 最长连续公共子序列 5.9 x 354
1536
DP
Ugly Numbers
4.4 x 46
1494
DP
Coins
4.1 x 34
1425
DP
All in All
1.7 x 421
1279
DP
Compromise
6.5 x 11
1271 The Tower of Babylon 5.7 x 20
1226
DP
Stones Game
4.1 x 34
1203
DP
Piggy-Bank
6.3 x 14
1186
DP
Anniversary party
3.4 x 21
1163
DP
easy to do DP
3.3 x 170
1129
DP
考新郎
5.2 x 128
1113
DP
装箱问题
2.3 x 438
1111 数塔 2.5 x 308
1079 大话西游 5.0 x 1687
1053
DP
子集和问题
8.3 x 16
1052
DP
0-1背包问题
5.4 x 603
1051
DP
完全加括号的矩阵连乘积
6.3 x 226
1029
DP
走道铺砖
7.8 x 37
1027
DP
邮资的问题
6.8 x 122
1018
DP
单词的划分
3.9 x 119
1017
DP
Apple Catching
7.2 x 73
1015
DP
核电站
5.1 x 124
1009
DP
整数的拆分
5.7 x 434
1004
DP
A Mini Locomotive
4.6 x 84
100
DP
变换种类数
5.0 x 55
22 很大很大的数 6.9 x 19
19
DP
Teacher Panda and plagiarism
5.4 x 14
7
DP
Balls
5.3 x 11
标签云