动态规划问题总结

动态规划算法通常用于求解具有某种最优性质的问题。

其基本思想就是将问题分解成子问题,再对每个子问题求最优解,最后将其合并即可得到该问题的最优解。

虽然动态规划的思想很容易理解,但面对具体的问题时,也有难以下手。

刚开始解决动态规划问题时,总是会想着这个子问题应该如何求得最优解,这本身没问题,但有一点要注意,不要把子问题独立求解。

对于动态规划的问题来说,每个子问题的解都是相关联的,求当前的子问题的解应该借助之前求出的子问题的解。

通过结合具体的事例,看看如何使用动态规划的思想。

(以下事例都来自leetcode)

栗子一:爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

假设现在求 n 级台阶的最优解。

从题目可知,每次只能爬 1 或 2 个台阶,所以为了到达 n 级台阶,可以在 n-1 级台阶时走 1 步,或在 n-2 级台阶时走 2 步。

这样我们知道,n 级的最优解应该由 n-1 级和 n-2 级的最优解得出。

具体实现如下:

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

栗子二:打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

和上一题一样,我们先假设偷到第 n 个屋子,这时候最优解是多少?

还是先看看题目给的条件,因为有相连的防盗系统,所以不能偷相邻的(??)。

这样呢,对与第 n 个屋子,偷还是不偷?是一个选择。如果偷,就不能偷第 n-1 个屋子,总收益就是 n + (n-2),否则就是 n-1

于是问题就可以化简为比较 n + (n-2)  和 n-1 偷哪个赚得更多

具体实现如下:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==0)
            return 0;
        if(n==1)
            return nums[0];
        int dp[] = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        for(int i= 2;i<n;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

总结:

以上是动态规划思想的简单应用。要熟练运用动态规划,还是要多做题,挑战更困难的题目。不过,其核心思想并不会改变。

  • 本人水平有限,如有错误或建议,欢迎指正
  • 用支付宝打我
  • 用微信打我

Long may the sunshine

发表评论

电子邮件地址不会被公开。 必填项已用*标注

召唤蕾姆