阿里巴巴校招面試題目，還是不是十分確定，來問問大家

folklore

m*n+(m+n)/2

就是邊數(shù)除2？

@cjaizss
m和n同性，所以，公式中m,n一樣是對(duì)稱的。
你這個(gè)不對(duì)稱啊
錯(cuò)了，S之以免誤導(dǎo)人家

cjaizss

folklore 發(fā)表于 2012-10-29 00:38
m*n+(m+n)/2

就是邊數(shù)除2？

C(m+n,n)對(duì)m,n對(duì)稱的
C(m+n,n)=(m+n)!/(m!*n!)

folklore

回復(fù) 12# cjaizss


    你說得對(duì)，我搞錯(cuò)了， C(m+n,m)=C(m+n,n)
就是共要走m+n步，其中m步向上，（或n步向右）

pandaiam

Ager好厲害.

InMySin

回復(fù) 3# Ager
這個(gè)也有想到過，但是復(fù)雜度有點(diǎn)高，
求一個(gè)路徑的 00...11 中的1的計(jì)算量為 m+n; 然后需要進(jìn)行 2^(m+n) 次比較， 會(huì)可能到達(dá) (m+n)*2^(m+n)，這樣復(fù)雜度有點(diǎn)高。。
一是要改進(jìn)計(jì)算1的個(gè)數(shù)的方法（可不可以參考計(jì)算一個(gè)二進(jìn)制數(shù)中1的個(gè)數(shù)，CU就出現(xiàn)過，很神奇方法）

   

isaacxu

一種是套公式：Path(m,n) = C(m+n,n) = C(m+n,m)

另一種是相當(dāng)于解一個(gè)Pascal Triangle

1..4..10..20..35
1..3..6...10..15
1..2..3...4...5
1..1..1.. 1...1

evaspring

尼瑪，搞程序這么累，操，真心想轉(zhuǎn)行了

InMySin

回復(fù) 16# isaacxu
哦哦，原來有叫 pascal triangle，其實(shí)就是動(dòng)態(tài)規(guī)劃？
假設(shè) m x n 的，然后
f( m , n ) = f( m-1 , n ) +  f( m , n-1 )             |這個(gè)問題可以遞歸來解決，第一步選上，就變成 (m-1)xn 的網(wǎng)格走 ； 第二步選右就變成 m x (n-1) 網(wǎng)格走，然后根據(jù)分類原理所以 f( m , n ) = 兩個(gè)加起來.

初始條件 f( 0 , n ) = 1 ; f( m , 0 ) = 1;
然后就可以動(dòng)態(tài)了。。。

但是，如何將這個(gè)f( m , n ) == 變換成 C( m+n , n ) ...數(shù)學(xué)學(xué)不好，哎

   

InMySin

回復(fù) 5# pmerofc


    計(jì)算總次數(shù)理解了，我其實(shí)更像確認(rèn)的是那個(gè)打印所有路徑的方法

captivated

mark......