DP

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

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

# 标题 奖励 解出人数
3653 她的名字 4.2 x 195
3647 小猪分类 8.0 x 7
3568
DP
棋盘染色
9.4 x 3
3563
DP
校园卡清零
6.1 x 38
3544
DP
小迷妹在哪儿
3.5 x 174
3543 夜游 ECNU 4.8 x 40
3531
DP
定西
1.4 x 734
3507 坑爹的售票机 (Easy) 2.4 x 428
3489 坑爹的售票机 4.8 x 113
3483 最小 OR 路径 (EASY) 4.9 x 62
3479
DP
现任总统的巡游
6.6 x 11
3470
DP
Zoltan
9.9 x 1
3447
DP
比昨天更多的棒棒糖 (Hard)
4.9 x 28
3446 骰子点数之和问题 4.7 x 120
3438
DP
棋盘上的車
6.4 x 7
3437
DP
卡车运输
5.6 x 9
3432
DP
Smooth Array
8.5 x 2
3395
DP
铺瓷砖问题
9.1 x 3
3373 骑士游戏 7.2 x 5
3365 打字员吉吉木 6.8 x 9
3355 开心消消乐 4.4 x 69
3354 领外卖 3.5 x 153
3338
DP
双塔问题
3.4 x 128
3330 沉陷过往的幻灭 6.1 x 10
3329
DP
奇异收缩的剪影
4.5 x 23
3302
DP
打印
2.3 x 345
3297 铺瓷砖 1.8 x 258
3281
DP
找不到路哒 ultmaster
3.4 x 104
3267
DP
足球锦标赛
2.4 x 347
3261 分词 3.9 x 101
3257 七减一 5.0 x 87
3227 声控开关 (Hard) 3.0 x 70
3226 声控开关 (Easy) 3.0 x 84
3133 最长回文子串 1.5 x 270
3072 小巴菲特买股票 1.1 x 369
3051
DP
台阶走法数
2.6 x 323
3034 数字拆分 1.9 x 321
3029 不重复正整数 1.0 x 313
3010
DP
Coins (III)
4.0 x 34
3009
DP
Coins (II)
2.9 x 42
3008
DP
Coins (I)
3.5 x 56
3005 小型组合数 2.1 x 656
2999 计算多项式的系数 1.8 x 555
2958
DP
求上升子序列和的最大值
1.2 x 494
2922 Minimizing maximizer 7.5 x 6
2921
DP
Corn Fields
7.8 x 6
2920
DP
Mondriaan's Dream
5.1 x 18
2857
DP
编辑距离
2.1 x 437
2854 统计特定字串模式的个数 0.8 x 559
2846 统计字符串个数 0.3 x 927
2799
DP
区间覆盖
4.0 x 23
2798 斐波那契数列和 3.0 x 106
2743
DP
Stock Exchange
4.2 x 34
2726
DP
Recursively Palindromic Partitions
4.9 x 12
2686 Matchsticks 4.7 x 24
2585
DP
0-1 Package
3.3 x 120
2527 Fj & haozi 1.6 x 545
2441
DP
Legendary Brave, TOKOSHI
6.3 x 11
2307
DP
Pirates’ Gold
7.0 x 11
2245 DNA Laboratory 9.9
2233
DP
Strange Towers of Hanoi
4.4 x 12
2212
DP
Lecture halls reservation
8.2 x 5
2211
DP
The number of n-k-special sets
7.9 x 4
2168 Game Dice 8.8 x 4
2083
DP
ZigZag
2.2 x 198
2075
DP
汉堡大赛
6.3 x 7
2074
DP
Ant Counting
6.2 x 9
2064
DP
Bookshelf 2
3.7 x 54
2042
DP
Eating Together
4.8 x 24
1976
DP
Common Subsequence
5.1 x 21
1843 津津骑马 3.8 x 121
1825
DP
数塔IV
2.9 x 109
1824
DP
数塔III
2.0 x 276
1823
DP
数塔II
3.9 x 144
1805 最长连续公共子序列 3.5 x 496
1536
DP
Ugly Numbers
4.1 x 58
1516
DP
Unidirectional TSP
7.9 x 6
1494
DP
Coins
4.1 x 39
1425 All in All 1.3 x 592
1279
DP
Compromise
6.6 x 11
1271 The Tower of Babylon 5.6 x 22
1255
DP
Brackets sequence
4.5 x 18
1238 加分二叉树 4.4 x 72
1226
DP
Stones Game
3.9 x 42
1203
DP
Piggy-Bank
5.6 x 21
1186 Anniversary party 3.5 x 26
1163 easy to do DP 3.1 x 196
1129
DP
考新郎
5.0 x 145
1113
DP
装箱问题
2.0 x 545
1111 数塔 2.0 x 393
1079 大话西游 1.3 x 1932
1053
DP
子集和问题
7.9 x 22
1052
DP
0-1背包问题
1.3 x 799
1051
DP
完全加括号的矩阵连乘积
2.8 x 321
1029
DP
走道铺砖
4.1 x 80
1027
DP
邮资的问题
3.7 x 139
1018 单词的划分 2.8 x 238
1017
DP
Apple Catching
4.3 x 78
1015
DP
核电站
4.3 x 189
1012
DP
The 3n + 1 problem
6.2 x 66
标签云