动态规划刷题

动态规划刷题

Scroll Down

最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大和为 6。

思路

假设dp[i]表示以nums[i] 结尾的最大子段和
例如数组:[-2,1,-3,4,-1,2,1,-5,4]
dp[0]初始值为nums[0],即当数组只有一个元素时。
dp[1]在这里表示以nums[1]结尾的最大子段和,
dp[1] = max(dp[1 - 1] + nums[1], nums[1]);
因为必须以nums[1]结尾,所以存在两种可能:

  • 前面的子段+nums[1]
  • nums[1]:前面的子段全部舍去,只剩nums[1]

则可以得出转移方程:dp[i] = max(dp[i - 1] + nums[i], nums[i])

所以最后要求的最大子段和就是以某个元素结尾的最大子段和

class Solution {
    public int maxSubArray(int[] nums) {
        // dp[i] 表示以nums[i]结尾的最大子段和
        int []dp = new int [nums.length + 1];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

爬楼梯

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

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

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

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

思路

假设 dp[i] 为爬到第i层的最多方式数
由于每次只能趴1或2个台阶,所以
爬到第i层的最多方式数 = 爬到i - 1层的最多方式数 + 爬到i - 2层的最多方式数
可以得到转移方程为:dp[i] = dp[i - 1] + dp[i - 2]

class Solution {
    public int climbStairs(int n) {
        // dp[i] 表示 爬到第i层的最多方式数
        int []dp = new int [n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

打家劫舍

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

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

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路

假设 dp[i] 表示前i间房间能偷窃到的最高金额
因为不能偷窃相邻的两间房间,所以偷窃到第 i 间房间所能获得的最高金额有两种情况:

  • 有偷第 i 间房间
  • 没有偷第 i 间房间
    如果偷了第 i 间房间,那么就不能偷第 i - 1间房间,所以最高金额 = 偷第i - 2间房间的最高金额 + 第 i 间房间的金额
    如果没有偷第 i 间房间,那么最高金额 = 偷第 i - 1间房间的最高金额

可得转移方程:dp[i] = max(dp[i - 1], dp[i - 2] + 第 i 间房间的金额)

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int []dp = new int [nums.length + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}
支付宝 微信