algorithm - 计算递归关系 p(m, n) = p(m-1, n-1) + p(m-1, n)

Question

给定一个递归方程p(m, n) = p(m-1, n-1) + p(m-1, n)。我必须为 1 ≤ m，n ≤ 10⁵ 计算 p(m, n)。问题是，对于较大的 m 和 n 值，递归算法会导致超时，并且由于巨大的内存需求而无法完成内存。

这个问题应该怎么解决？基本情况:p(1, n) = 1 和 p(n, 1) = n

Answer 1

summing over a row of binomial coefficients 中 Pascal's triangle 的 O(k) 运行时复杂度的解决方案:

function sumbincoef(n, k) {
  var bincoef = 1, sum = 1;
  for (var i = 1; i <= k; ++i) {
    bincoef = bincoef * (n - i + 1) / i;
    sum += bincoef;
  }
  return sum;
}

function p(m, n) {
  return sumbincoef(m - 1, n);
}

console.log(p(10000000, 50)); // 3.287546666914557e+285

The above result for p(10000000, 50) is the best possible 64-bit float representation for 3287546666914557308694953621332468056786361676360499868634585863380466725155646219866201991329567029752979948424340585220003362046032042304860695097308112596244670197867704848935084227060330672914092328758709997221191832805084217964476100165465190964311176563705979858704659291260737501 provided by JavaScripts Number datatype .

如果你想要未截断的结果，你可以使用 math.js 或 e 提供的 BigNumber 数据类型。 G。使用内置无限整数精度的语言，例如 python:

def sumbincoef(n, k):
  bincoef = 1
  sum = 1
  for i in range(1, k + 1):
    bincoef = bincoef * (n - i + 1) / i
    sum += bincoef
  return sum

def p(m, n):
  return sumbincoef(m - 1, n)

p(100000, 100000) 的结果计算如下:

499501046507192253972016382165016795490214569527090845885764636931572916232128674163743665666224825201582197222777927465009399830382808828145423567712374643759944481493683554662317521368655623963290013926562054436854280264361419508228434551342533796175895734852642882234840076241617273777162514639326040347888548587055111602148817560266538899844896255830993538589288797776086004066014760230897461462964781196048289893677907933376274789865657240312463013091897065254029134301576756708936981141749544317887903105230331818606529389766117248600540424318477070091792567992901780178701093645407778329030359323063448641989731092113378967481944667862379438097956882838120556251035435243523258969819935505460018196737280904530080668894928014843179927901238072446652352611143006568854797917865974294924820228619193758535112116631671844721164869093886657664347210896806265095393445180183164158075136306996707640203558595746195167093746769722794815064609862820885861677177237577618965544613409120122637787604735232109297193143281637211566604237111077574665750135887503211441310591127467480027872866748233924163459047594797788458725483661220887021642022794105456895268782338606998831089263252858492741728124375916119162515932275273605718496708399083908512756140648903259740314770266957732873997064874959517425377216820725281582869800334669121365821701979006064013049210612375710391735611241570515203430185982008092787082821973612673247262485015725494504658113447637221435273821273612658375726059111572769418715411632110031651256876656468258217086260312807765589736930957145238072282746356420908759176566352648774768528071911978661396983651505303872842423871391609767461399191821808188237148477295333618456206816296606166782156794723260955094106191487045395819301161772547969438336820161478899695057607722400181860753455779555599800076529455386471051611521213101784674660802646378481292922291117729732263846155409865290314016325836822467188086620487667116664486514147958678463650664321165587980261524758583851658185476112847623020107169382759882200826407401117416594054877971098023823969426009927050867449297425550273462330861707156765496920296163447679326944348721350430351431775104278101477467624002539826078245984163255337205048391147597708080885877149876000494365368893810534294538548470580521901431197522266189479593538014463019674491305038744383642645905323424457194682453239229560580609665035395026852952109400642827970184953544401648343580582798061616599915546161254143309016094021972378649338104846790989219296398462506166346759734660386216776368278312411189391694403749963841581672015930223180935189489215651642191173520547215329573596417059548759261960616383719249528078184421646951972100130876548842530256646855072454319807081027802677366778496335047068763591457120361713396878253488278373796705065511267141504020453979366477210677565365102508579921211538023460486645364507080317698044027960117868844282392612004638855574456724620849780358589314921826698909043473705337555567676185577021829965544484874282940044393098746717896462310202588362300612530920200598314493633690153524918060898724233955037392317809733241461236806705756778358964589098402802686324207056417392912062956097730059220620467489148165852100126520933084748115936793032624270511110593477211189414459485604025728757068098240268486158228528249923976882858727406429870303866957938766617760780471795963759967550711112348150850685870966875245964768164755055764647591814140959591082583822797325791402449212805837407518390263393933135849982464847468852289743807331405546499101036850666516222550269268927559440173707409933255728966134245049650011836808427764708672102996268598262249896274157967185317198518590480573516153709349251752736114451358742516668416415014056645542084657522869496659196729664649747139800765487805935445946476422453712164238350312158558581136588330339805098390110228229450794976235237050057905548181686566469417843447470437966708845469390319929232365029446408799942223874306503157653438003504241863376389488867841502138945138605284191651073513986429766816605528203213195486228997484308145400980207087696788443829399621427495607586896213517162432420712372841944477094662072549375287970150662484877084847766514844010965243708175054896001810511938413758818499048880748981804835217407006206534178843995249871829814824785272976236769100018188516244749105166566645678115758492720520765852709696411736169942422677608660184404415605047197071746914110177482514076537554354930234061240148691281562249466598264810118630429325452515399665432600061583595759138287104784475656809204770606073689315552144885893072407915848292438347477741312625248061352235735611481013734118145490193873468849367947106272089617764919373991522512695489436673486630154877207823740273686636638362432637951749766817706347695022942749434178746393230762602040024505739294614454272167699849739043373580675989291928572821079158559650205899472039513417317877516994404336256394178864881324960691371828699646365111939628846211639274360064862769303598415189124153186294990424231925191417812920195865593634719073227682584503126501160879567154237760795073764957460764847218118345541661684688399656910463793501212311916560911835761838604920859385193008615426122402158816680137986658060063112416154266464449307727961071368925370548941112236475633178611278358488970488367077150864463416631753872560508393456066723284036989868635573095964996905908941377071089646344189514271545497122063025597292461895498316477513193285055744207113308148490503682635546425228973543075404702728889893215075244997931708235026411028139300443201285471622212702201712157010190603742876899950803323276049349039529467366012152531795368191076064030002091376466274262396395211786379928710477731618191546621412535575940088781686990576188099734313163527531754992562716693779730077045043100714681283686916584654116442716350074373831755941544258688763440976318008267295027808038385672680882772548721248953803195304665001420848242379701352333473424329681821271431262082241832608696129326423712247618165115265570672466616991116827580571573456595008524411341826295819986195631330807010285399836369176479873956274448070964363062987878085079632291177057596108862695982551717239684018452850190652827893315550573815659478577816825936387899595443144538274747600973746107442570853962617619714690085057474261950292217916487438463997079319232043863295087455246661942673271498962695028065578114412057359607906860506013369982431141580521514363436992016757106014975830542309658234403797226348262428503527722607627374672521742645899375609298682359523075770679129106952008605914785116376851369489389675345202246927679382525177857793643660079844253066557273855078784968772054874668705799559955748136340085901947545390152059220003779273428048848283479216281364166370820902229536392234002568038707714420635622817669181273453446821545103410837522990966087225668145692699157728030522984630225439385015209228957673914586288140531636105401791303045228623030960211879018157360007937453768081689262173114938495894390433572696442328620861175244388340193472673729441595379867764640035462073568534832351476535025354154570624638570238809672950365760311681711306406853725208126023672479870783944100192272338719447518959617229708562275511586949751517421096854404166485455408828050535434657901034753......(Stackoverflow wouldn't accept that many figures)......35584033065631459417382400319827381172596270290200128863975429530908663000094178338788124817542256133205278775822567235131041742740388086850961813203192415685921043738611547233989330610824844921161394624381302583949343237869506130180533962330864195008133672029951612013268171775150776491632259932940651971293308867493640115946272139008056659177138051629001196971303929378474742559650357926964921581983787765676242110637407432013648653577728554711716235928485261817836143275758132836194624040329639724476539354076803333370657299130399405639377328156503892871742094805404749559718018780537663179707071738441247346265393895346637645447954972532636035989709841370920409915283748844043118230409672811818851233907536566733098961559969558597989676416558748410250288649969283238492130407759470433388160427741579918094425224169955675752566454851995044459531566687902047443477947732956324052267310715147866687996449479664832222343450324337265830939410648597073095957066489336687641851497595353089962089070124678142503268136885818177784860001623498065332641225847583636580915696933779395639132466879020005529605686135419561759229854553740334926348040454590936489250787032272274132235539316693299556594405068873159492248372994505770167129657673870041055367409235760626687253635769065524148306489540738831634895697285178695268711384889816905784198111604201298512577652367194941554688