首页 > 其他 > 详细

LintCode "k Sum" !!

时间:2015-10-30 02:00:44      阅读:268      评论:0      收藏:0      [点我收藏+]

Great great DP learning experience:
http://www.cnblogs.com/yuzhangcmu/p/4279676.html

Remember 2 steps of DP: a) setup state transfer equation; b) setup selection strategy.

a) States

From problem statement, we find 3 variables: array size, k and target. So it is 3D DP:

dp[i][j][t]: in previous i elements, we pick j of them, to reach value t - number of results

b) Selection Strategy

Usually for 1D array, selection strategy is very simple: with A[i] - pick it or not. Combined with step a, dp[i][j][t] is result of the 2 choices - pick or not:

dp[i][j][t] = dp[i-1][j-1][t-A[i]](pick it) + dp[i-1][j][t](no pick)

Optimization: dimension i can be eliminated.

Details: To start: all dp[*][0][0] = 1

LintCode "k Sum" !!

原文:http://www.cnblogs.com/tonix/p/4922254.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!