數(shù)據(jù)結(jié)構(gòu)和算法—?jiǎng)討B(tài)規(guī)劃

我一直最想做的就是機(jī)器學(xué)習(xí)，所以也都是在報(bào)機(jī)器學(xué)習(xí)的崗位，在BAT三家公司中，其實(shí)還是要講百度吧，因?yàn)榘⒗镌谝幻娴臅r(shí)候就掛了，給我的理由是我投錯(cuò)了崗位(據(jù)面試官講我應(yīng)該去投算法崗，但我投的是數(shù)據(jù)挖掘)，后來我在想，其實(shí)還就是我沒能達(dá)到她的語氣要求；騰訊就別講了，連面試都沒收到(據(jù)說這個(gè)崗位不招我們學(xué)校的)，這可能就是個(gè)猜測(cè)吧。重點(diǎn)說說百度的筆試和面試吧，單純從技術(shù)上來講，因?yàn)槲以谧?a href='/map/jiqixuexi/' style='color:#000;font-size:inherit;'>機(jī)器學(xué)習(xí)嘛，百度還是我最心儀的公司。這次百度的招聘分為筆試+面試(三個(gè)技術(shù)面+Hr面)，我掛在了最后一個(gè)技術(shù)面上，先來說說武漢的筆試吧，當(dāng)然筆試題我做得還是蠻開心的，因?yàn)樽詈笠坏雷C明題可以說還是我平時(shí)的強(qiáng)項(xiàng)吧，面試中，前兩面都還好，面得比較基礎(chǔ)，包括基本的數(shù)據(jù)結(jié)構(gòu)，算法，然后是機(jī)器學(xué)習(xí)的算法理解，不同算法之間的對(duì)比，這也正是我平時(shí)做的一些工作，這樣的過程還是蠻舒服的，整個(gè)流程下來，我覺得問題不是很大。最后一關(guān)就是很多實(shí)際的項(xiàng)目問題，由于我自己平時(shí)項(xiàng)目較少，加之自己的導(dǎo)師不是做機(jī)器學(xué)習(xí)的，沒做過具體的機(jī)器學(xué)習(xí)相關(guān)項(xiàng)目，只是將算法學(xué)習(xí)的比較全。
    我寫以上的東西也是給找工作的朋友一個(gè)建議，也是給自己一個(gè)醒目的教訓(xùn)，多去實(shí)踐，所以這段時(shí)間我還是會(huì)努力更新我的博客，當(dāng)然不完全是前面的機(jī)器學(xué)習(xí)算法，現(xiàn)在將包括更多的東西，我會(huì)把我現(xiàn)在在做的項(xiàng)目也慢慢更新上來，然后又基本的算法的學(xué)習(xí)材料，希望關(guān)注我博客的朋友，大家一起努力，我不是科班出身，但是我希望大家不吝賜教，有你的幫助我會(huì)成長的更快。
    好了，就寫到這吧。我想還是從一些算法開始入手吧，今天還是來更新一篇?jiǎng)討B(tài)規(guī)劃的文章。
一、動(dòng)態(tài)規(guī)劃的思想
    動(dòng)態(tài)規(guī)劃(dynamic programming)是一種算法設(shè)計(jì)的思想，主要是將一個(gè)問題劃分成幾個(gè)更小的問題，并對(duì)這樣更小的問題進(jìn)行求解，最終得到整個(gè)問題的解。有人在想這樣的方式和分治法的求解很像。
動(dòng)態(tài)規(guī)劃：各個(gè)子問題不是獨(dú)立的，他們包含了公共子問題
分治法：一個(gè)大問題是被劃分成一些獨(dú)立的子問題，通過遞歸地求解子問題最終得到整個(gè)問題的解
在動(dòng)態(tài)規(guī)劃法中，與其對(duì)交疊的子問題一次一次求解，不如對(duì)每個(gè)較小的子問題只求解一次并把結(jié)果記錄在表中，這樣就能從表中得到原始問題的解。舉個(gè)簡單的例子，對(duì)于菲波那切數(shù)列來說：

對(duì)于這樣的遞推式，可以把一個(gè)復(fù)雜的問題分解成幾個(gè)非獨(dú)立的子問題，我們可以采用的方式是記錄每一組值，如斐波那契數(shù)列的值依次是0,1,1,2,3,5，...。而不需要重復(fù)去計(jì)算。
二、用動(dòng)態(tài)規(guī)劃求解二項(xiàng)式系數(shù)
二項(xiàng)式系數(shù)問題是一個(gè)求解的問題。我們有如下的遞推式：

要計(jì)算的值，我們需要記錄到之間的值。動(dòng)態(tài)規(guī)劃的核心思想就是要找到這樣的遞推式，然后構(gòu)建這樣的存儲(chǔ)空間去記錄中間的值，避免重復(fù)計(jì)算。最簡單的方式是利用數(shù)組去記錄。數(shù)據(jù)分析師培訓(xùn)
如上的問題可以用下面的Java代碼實(shí)現(xiàn)：
[java] view plain copy 在CODE上查看代碼片派生到我的代碼片
package org.algorithm.dynamicprogramming;  
 
/**
 * 利用動(dòng)態(tài)規(guī)劃的思想去求解二項(xiàng)式系數(shù)的問題
 *  
 * @author dell
 *  
 */  
 
public class CalculateDemo {  
    /**
     * 用動(dòng)態(tài)規(guī)劃計(jì)算C(n,k)
     *  
     * @param n為二項(xiàng)式的參數(shù)
     * @param k為二項(xiàng)式的參數(shù)
     * @return C(n,k)的值
     */  
    public static int calBinomial(int n, int k) {  
        int C[][] = new int[n+1][k+1];  
        for (int i = 0; i <= n; i++) {  
            for (int j = 0; j <= minValue(i, k); j++) {  
                if (j == 0 || j == i) {  
                    C[i][j] = 1;  
                } else {  
                    C[i][j] = C[i - 1][j - 1] + C[i - 1][j];  
                }  
            }  
        }  
        return C[n][k];  
    }  
 
    // 返回較小的值  
    public static int minValue(int i, int k) {  
        return (i <= k ? i : k);  
    }  
 
    public static void main(String args[]) {  
        int n = 10;  
        int k = 5;  
        System.out.println(calBinomial(n, k));  
    }  
 
}