LeetCode 總結(jié) - 搞不定 Dynamic Programming 面試題

emmm...動態(tài)規(guī)劃就練幾個簡單的題吧，其他的搞不定遍烦，告辭告辭~

如何想到使用DP

  • 找最大值/最小值(maximum/minimum)
  • 判斷是否可行(yes/no)
  • 所有可能結(jié)果的數(shù)量(count)

解題思路

Matrix DP

[120] Triangle

自底向上：

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle.size() == 1) return triangle.get(0).get(0);
    int n = triangle.size();
    int[][] dp = new int[n][n];
    // 先算出最底層的值
    for (int i = 0; i < triangle.get(n - 1).size(); i++) {
        dp[n - 1][i] = triangle.get(n - 1).get(i);
    }
    // 自底向上
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j);
        }
    }
    return dp[0][0];
}

自頂向下：

public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle.size() == 1) return triangle.get(0).get(0);
    int n = triangle.size();
    int[][] dp = new int[n][n];
    dp[0][0] = triangle.get(0).get(0);
    // 先要初始化對角線所有點以及左側(cè)邊界所有點
    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
    }
    // 自頂向下
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
        }
    }
    // 結(jié)果要在最后一行里找最大值
    int res = dp[n - 1][0];
    for (int i = 1; i < n; i++) {
        res = Math.min(res, dp[n - 1][i]);
    }
    return res;
}

參考講解：

[62] Unique Paths

public int uniquePaths(int m, int n) {
    if (m == 0 || n == 0) return 0;
    int[][] dp = new int[m][n];
    // 初始化：第1行和第1列某個位置的來源都只有一種情況
    // (0,j-1)->(0,j), (j-1,1)->(j,1)
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // 要么從上邊來烟瞧，要么從左邊來
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

[63] Unique Paths II

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    if (m == 0 || n == 0) return 0;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 0) dp[i][0] = 1;
        else break;
    }
    for (int j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 0) dp[0][j] = 1;
        else break;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            else dp[i][j] = 0;
        }
    }
    return dp[m - 1][n - 1];
}

[64] Minimum Path Sum

public int minPathSum(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];
    // 初始化
    dp[0][0] = grid[0][0];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

Sequence DP

[70] Climbing Stairs

問題：爬樓梯要爬n步才能到達(dá)樓頂绣溜，每次只能爬1步或者2步竞漾，一共有多少種方式爬到樓頂放钦？

思路：斐波那契數(shù)列的典型應(yīng)用岩榆。
0級臺階：0
1級臺階：1
2級臺階：2
3級臺階：1+2=3
4級臺階：2+3=5
......
n級臺階：f(n-2)+f(n-1)=f(n)
令dp[i]表示爬到第i階樓梯可行的不同方式數(shù)目错负，接著尋找當(dāng)前子問題dp[i]與前面子問題的關(guān)系。

  • 如果是用兩步跳過來的（爬到第i階樓梯）則dp[i]=dp[i-2]勇边，因為這兩步已經(jīng)確定了犹撒，那么只有dp[i-2]種可能
  • 如果是用一步跳過來的（爬到第i階樓梯）則dp[i]=dp[i-1]，因為這一步已經(jīng)確定了粒褒，那么只有dp[i-1]種可能
public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    // 初始條件：一級樓梯是一種解法识颊，兩級樓梯是兩種解法
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        // 可以從第i-1層階梯過來，也可以從第i-2層階梯過來奕坟，那么到達(dá)第i層階梯的方法數(shù)是兩個的和
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

由于動態(tài)規(guī)劃的時候只用到了前面2步祥款，因此可以用兩個變量記錄一下，這樣就將空間復(fù)雜度降到O(1)了执赡。

public int climbStairs(int n) {
    int result = 0;
    int num1 = 0, num2 = 1;
    for (int i = 1; i <= n; i++) {
        result = num1 + num2;
        num1 = num2;
        num2 = result;
    }
    return result;
}

參考講解：

[55] Jump Game

public boolean canJump(int[] nums) {
    boolean[] dp = new boolean[nums.length];
    dp[0] = true;
    for (int i = 1; i < nums.length; i++) {
        // 枚舉上一步跳到哪兒了镰踏，也就是i可以是從哪個j跳過來的
        for (int j = 0; j < i; j++) {
            if (dp[j] && j + nums[j] >= i) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[nums.length - 1];
}

public boolean canJump2(int nums[]) {
    int maxLocation = 0;
    for (int i = 0; i < nums.length; i++) {
        // 如果先前的maxLocation小于i，意味著不能到達(dá)i位置,因此返回false
        if (maxLocation < i) return false;
        // greedy
        maxLocation = (i + nums[i]) > maxLocation ? i + nums[i] : maxLocation;
    }
    return true;
}

[300] Longest Increasing Subsequence

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    // dp[i]表示前i個數(shù)并且第i個數(shù)是LIS中最后一個數(shù)的最長LIS的長度
    int[] dp = new int[n];
    int max = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        // 枚舉倒數(shù)第二個數(shù)是什么
        for (int j = 0; j < i; j++) {
            // 前面的數(shù)比第i個數(shù)小沙合，滿足遞增條件
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

Two Sequences DP

[72] Edit Distance

問題：給出兩個單詞word1和word2奠伪，計算出將word1 轉(zhuǎn)換為word2的最少操作次數(shù)跌帐。你總共三種操作方法：插入一個字符、刪除一個字符绊率、替換一個字符谨敛。

思路：

public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    // dp[i][j]表示word1的第i個字符匹配上word2的前j個字符
    int[][] dp = new int[m + 1][n + 1];
    // 刪掉i個字符
    for (int i = 0; i < m + 1; i++) dp[i][0] = i;
    // 刪掉j個字符
    for (int j = 0; j < n + 1; j++) dp[0][j] = j;
    // 枚舉word1的所有位置
    for (int i = 1; i < m + 1; i++) {
        // 枚舉word2的所有位置
        for (int j = 1; j < n + 1; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[m][n];
}

[LintCode 77] Longest Common Subsequence

問題：給出兩個字符串，找到最長公共子序列(LCS)滤否，返回LCS的長度脸狸。

思路：

public int longestCommonSubsequence(String A, String B) {
    int m = A.length();
    int n = B.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            if (A.charAt(i - 1) == B.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    }
    return dp[m][n];
}

[322] Coin Change

問題：給定一組硬幣和一個目標(biāo)金額，返回最少用幾個硬幣能湊出目標(biāo)金額藐俺，如果不能返回-1炊甲。

思路：數(shù)組dp用來記錄能湊出從1到amount最少的硬幣數(shù)量。

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        // dp[i]表示湊齊錢數(shù)i需要的最少硬幣數(shù)
        dp[i] = Integer.MAX_VALUE;
        for (int j = 0; j < coins.length; j++)
            if (i >= coins[j] && dp[i - coins[j]] != Integer.MAX_VALUE)
                // 用當(dāng)前的硬幣能組合成啥欲芹，取最小
                // dp[i + coins[j] ] = min(dp[i + coins[j] ] , dp[i] + 1）
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

參考講解：

[746] Min Cost Climbing Stairs 爬樓梯的最小代價

問題：我們爬樓梯卿啡，每一步都會有代價，例如第i步代價為cost[i]菱父，你可以從第0個臺階爬起颈娜，也可以從第一個臺階爬起，同時浙宜，每次你可以跳一步官辽，也可以跳兩步。求爬完樓梯的最小代價是多少粟瞬。

思路：

  • Recursion + Memorization 記憶化遞歸
    dp[n]表示爬到第n階樓梯的最小代價同仆，我們來思考一下如何才能到第n層呢？是不是只有兩種可能性亩钟，一個是從第n-2層上直接跳上來乓梨，一個是從第n-1層上跳上來。那么dp[n] = min(dp(n-1)+cost[n-1], dp(n-2)+cost[n-2])清酥，也就是說我可以從第n-1階爬1步到達(dá)第n階樓梯，但需要cost[n-1]的代價蕴侣；我也可以從第n-2階爬2步到達(dá)第n階樓梯焰轻，但需要cost[n-2]的代價。最后我們返回最后一個數(shù)字dp[n]即可昆雀。
public int minCostClimbingStairs(int[] cost) {
    int m[] = new int[cost.length + 1];
    return dp(cost, m, cost.length);
}

private int dp(int[] cost, int[] m, int i) {
    // 在第0階或第1階開始爬是不需要代價的
    if (i <= 1) return 0;
    // 已求解過子問題辱志，直接返回
    if (m[i] > 0) return m[i];
    return m[i] = Math.min(dp(cost, m, i - 1) + cost[i - 1],
            dp(cost, m, i - 2) + cost[i - 2]);
}
  • DP
// DP，空間復(fù)雜度O(n)
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    // dp[i]表示爬到第i階樓梯的最小代價
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        // 要到達(dá)第i階樓梯狞膘，可以從第i-1層上花cost[i-1]爬一步上來揩懒，也可以從第i-2層上花cost[i-2]爬兩步上來
        dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

// 滾動數(shù)組，空間復(fù)雜度O(1)
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int dp1 = 0;
    int dp2 = 0;
    for (int i = 2; i <= n; i++) {
        int dp = Math.min(dp1 + cost[i - 1], dp2 + cost[i - 2]);
        dp2 = dp1;
        dp1 = dp;
    }
    // 因為dp1是最后的dp
    return dp1;
}

參考講解：

[LintCode 20] Dice Sum

http://lintcode.com/en/problem/dices-sum

問題：扔n個骰子挽封，所有骰子朝上一面的點數(shù)之和為s已球。輸入骰子個數(shù)n，求點數(shù)之和為s出現(xiàn)的概率。

思路：假設(shè)dp(n,x)表示投第n個骰子的時候智亮，點數(shù)之和為x出現(xiàn)的次數(shù)忆某，投第n個骰子的點數(shù)之和只與投第n-1個骰子有關(guān)。我們得到遞歸方程：
f(n,x)=f(n-1,x-1)+f(n-1,x-2)+f(n-1,x-3)+f(n-1,x-4)+f(n-1,x-5)+f(n-1,x-6)阔蛉，表示本輪點數(shù)之和為n出現(xiàn)次數(shù)等于上一輪點數(shù)之和為n-1,n-2,n-3,n-4,n-5,n-6出現(xiàn)的次數(shù)之和弃舒。

public double probability(int n, int x) {
    // dp(n,x)表示投第n個骰子的時候，點數(shù)之和為x出現(xiàn)的次數(shù)状原，投第n個骰子的點數(shù)之和只與投第n-1個骰子有關(guān)
    int[][] dp = new int[n + 1][6 * n + 1];
    // 初始化n＝1的情況
    for (int j = 1; j <= 6; j++) {
        dp[1][j] = 1;
        System.out.println("dp[" + 1 + "][" + j + "] = " + dp[1][j]);
    }
    for (int i = 2; i <= n; i++) {
        // i個篩子至少得到i點聋呢，至多得到6*i點
        for (int j = i; j <= 6 * i; j++) {
            // k表示最后一個篩子能取的點數(shù)
            for (int k = 1; k <= 6; k++) {
                // 表示本輪點數(shù)之和為n出現(xiàn)次數(shù)等于上一輪點數(shù)之和為n-1,n-2,n-3,n-4,n-5,n-6出現(xiàn)的次數(shù)之和
                if (j - k >= 0) dp[i][j] += dp[i - 1][j - k];
            }
            System.out.println("dp[" + i + "][" + j + "] = " + dp[i][j]);
        }
    }
    // 事件總數(shù)為6^n，dp[n][x]除以它就是發(fā)生的概率
    return dp[n][x] / (Math.pow(6, n));
}

而LintCode上是要我們求所有可能的x出現(xiàn)的概率：

public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    // dp(n,s)表示投第n個骰子的時候颠区，點數(shù)之和為s出現(xiàn)的次數(shù)削锰，投第n個骰子的點數(shù)之和只與投第n-1個骰子有關(guān)
    List<Map.Entry<Integer, Double>> results = new ArrayList<>();
    for (int s = n; s <= 6*n; s++) {
        // 要用long存儲，否則過不了后面大的Test Case
        long[][] dp = new long[n + 1][6 * n + 1];
        for (int j = 1; j <= 6; j++) {
            dp[1][j] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= 6 * i; j++) {
                for (int k = 1; k <= 6; k++) {
                    // 表示本輪點數(shù)之和為n出現(xiàn)次數(shù)等于上一輪點數(shù)之和為n-1,n-2,n-3,n-4,n-5,n-6出現(xiàn)的次數(shù)之和
                    if (j - k >= 0) dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        // 事件總數(shù)為6^n瓦呼，dp[n][s]除以它就是發(fā)生的概率
        double probability = dp[n][s] / (Math.pow(6, n));
        results.add(new AbstractMap.SimpleEntry<Integer, Double>(s, probability));
    }
    return results;
}

參考講解：

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末喂窟，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子央串，更是在濱河造成了極大的恐慌磨澡，老刑警劉巖，帶你破解...
    沈念sama閱讀 206,602評論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件质和，死亡現(xiàn)場離奇詭異稳摄，居然都是意外死亡，警方通過查閱死者的電腦和手機饲宿，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,442評論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門厦酬，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人瘫想，你說我怎么就攤上這事仗阅。” “怎么了国夜？”我有些...
    開封第一講書人閱讀 152,878評論 0贊 344
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵减噪，是天一觀的道長。 經(jīng)常有香客問我车吹，道長筹裕，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 55,306評論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任窄驹，我火速辦了婚禮朝卒，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘乐埠。我一直安慰自己抗斤，他們只是感情好囚企，可當(dāng)我...
    茶點故事閱讀 64,330評論 5贊 373
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著豪治，像睡著了一般洞拨。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上负拟，一...
    開封第一講書人閱讀 49,071評論 1贊 285
  • 城市分裂傳說
    那天烦衣，我揣著相機與錄音，去河邊找鬼掩浙。 笑死花吟，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的厨姚。 我是一名探鬼主播衅澈，決...
    沈念sama閱讀 38,382評論 3贊 400
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼谬墙！你這毒婦竟也來了今布？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,006評論 0贊 259
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤拭抬，失蹤者是張志新（化名）和其女友劉穎部默，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體造虎，經(jīng)...
    沈念sama閱讀 43,512評論 1贊 300
  • ?護(hù)林員之死
    正文 獨居荒郊野嶺守林人離奇死亡傅蹂，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 35,965評論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了算凿。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片份蝴。...
    茶點故事閱讀 38,094評論 1贊 333
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖氓轰，靈堂內(nèi)的尸體忽然破棺而出婚夫，到底是詐尸還是另有隱情，我是刑警寧澤署鸡，帶...
    沈念sama閱讀 33,732評論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布请敦，位于F島的核電站，受9級特大地震影響储玫，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜萤皂，卻給世界環(huán)境...
    茶點故事閱讀 39,283評論 3贊 307
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一撒穷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧裆熙，春花似錦端礼、人聲如沸禽笑。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,286評論 0贊 19
  • 一樁弒父案蛤奥，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽佳镜。三九已至，卻和暖如春凡桥，著一層夾襖步出監(jiān)牢的瞬間蟀伸，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 31,512評論 1贊 262
  • 情欲美人皮
    我被黑心中介騙來泰國打工缅刽， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留啊掏，地道東北人。 一個月前我還...
    沈念sama閱讀 45,536評論 2贊 354
  • 代替公主和親
    正文 我出身青樓衰猛，卻偏偏與公主長得像迟蜜，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子啡省，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 42,828評論 2贊 345