LeetCode 总结 - 搞不定 Dynamic Programming 面试题

emmm...动态规划就练几个简单的题吧，其他的搞不定，告辞告辞~

如何想到使用DP

  • 找最大值/最小值(maximum/minimum)
  • 判断是否可行(yes/no)
  • 所有可能结果的数量(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);
    // 先要初始化对角线所有点以及左侧边界所有点
    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);
        }
    }
    // 结果要在最后一行里找最大值
    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步才能到达楼顶，每次只能爬1步或者2步，一共有多少种方式爬到楼顶？

思路：斐波那契数列的典型应用。
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阶楼梯可行的不同方式数目，接着寻找当前子问题dp[i]与前面子问题的关系。

  • 如果是用两步跳过来的（爬到第i阶楼梯）则dp[i]=dp[i-2]，因为这两步已经确定了，那么只有dp[i-2]种可能
  • 如果是用一步跳过来的（爬到第i阶楼梯）则dp[i]=dp[i-1]，因为这一步已经确定了，那么只有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层阶梯过来，那么到达第i层阶梯的方法数是两个的和
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

由于动态规划的时候只用到了前面2步，因此可以用两个变量记录一下，这样就将空间复杂度降到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，意味着不能到达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个数并且第i个数是LIS中最后一个数的最长LIS的长度
    int[] dp = new int[n];
    int max = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        // 枚举倒数第二个数是什么
        for (int j = 0; j < i; j++) {
            // 前面的数比第i个数小，满足递增条件
            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 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符、删除一个字符、替换一个字符。

思路：

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

问题：给定一组硬币和一个目标金额，返回最少用几个硬币能凑出目标金额，如果不能返回-1。

思路：数组dp用来记录能凑出从1到amount最少的硬币数量。

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for (int i = 1; i <= amount; i++) {
        // dp[i]表示凑齐钱数i需要的最少硬币数
        dp[i] = Integer.MAX_VALUE;
        for (int j = 0; j < coins.length; j++)
            if (i >= coins[j] && dp[i - coins[j]] != Integer.MAX_VALUE)
                // 用当前的硬币能组合成啥，取最小
                // 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步到达第n阶楼梯，但需要cost[n-1]的代价；我也可以从第n-2阶爬2步到达第n阶楼梯，但需要cost[n-2]的代价。最后我们返回最后一个数字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，空间复杂度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++) {
        // 要到达第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];
}

// 滚动数组，空间复杂度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个骰子，所有骰子朝上一面的点数之和为s。输入骰子个数n，求点数之和为s出现的概率。

思路：假设dp(n,x)表示投第n个骰子的时候，点数之和为x出现的次数，投第n个骰子的点数之和只与投第n-1个骰子有关。我们得到递归方程：
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)，表示本轮点数之和为n出现次数等于上一轮点数之和为n-1,n-2,n-3,n-4,n-5,n-6出现的次数之和。

public double probability(int n, int x) {
    // dp(n,x)表示投第n个骰子的时候，点数之和为x出现的次数，投第n个骰子的点数之和只与投第n-1个骰子有关
    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表示最后一个筛子能取的点数
            for (int k = 1; k <= 6; k++) {
                // 表示本轮点数之和为n出现次数等于上一轮点数之和为n-1,n-2,n-3,n-4,n-5,n-6出现的次数之和
                if (j - k >= 0) dp[i][j] += dp[i - 1][j - k];
            }
            System.out.println("dp[" + i + "][" + j + "] = " + dp[i][j]);
        }
    }
    // 事件总数为6^n，dp[n][x]除以它就是发生的概率
    return dp[n][x] / (Math.pow(6, n));
}

而LintCode上是要我们求所有可能的x出现的概率：

public List<Map.Entry<Integer, Double>> dicesSum(int n) {
    // dp(n,s)表示投第n个骰子的时候，点数之和为s出现的次数，投第n个骰子的点数之和只与投第n-1个骰子有关
    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++) {
                    // 表示本轮点数之和为n出现次数等于上一轮点数之和为n-1,n-2,n-3,n-4,n-5,n-6出现的次数之和
                    if (j - k >= 0) dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        // 事件总数为6^n，dp[n][s]除以它就是发生的概率
        double probability = dp[n][s] / (Math.pow(6, n));
        results.add(new AbstractMap.SimpleEntry<Integer, Double>(s, probability));
    }
    return results;
}

参考讲解：

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,547评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,399评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,428评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,599评论 1赞 274
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,612评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,577评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,941评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,603评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,852评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,605评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,693评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,375评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,955评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,936评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,172评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,970评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,414评论 2赞 342