跳到主要内容

动态规划算法练习

动态规划（Dynamic Programming）通过将复杂问题分解为子问题，并存储子问题的解（记忆化/递推）来避免重复计算。其核心是确定状态定义和状态转移方程。

70. 爬楼梯 (Climbing Stairs)​

题目描述​

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题思路​

典型的斐波那契数列。由于第 n 阶台阶由于只能从 n-1 或 n-2 阶跳上来，所以 dp[n] = dp[n-1] + dp[n-2]。

Java 代码实现​

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int p1 = 1, p2 = 2;
        for (int i = 3; i <= n; i++) {
            int res = p1 + p2; p1 = p2; p2 = res;
        }
        return p2;
    }
}

118. 杨辉三角 (Pascal's Triangle)​

题目描述​

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

解题思路​

每一行第一个和最后一个元素是 1。中间的元素 res[i][j] = res[i-1][j-1] + res[i-1][j]。

Java 代码实现​

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) row.add(1);
                else row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
            }
            res.add(row);
        }
        return res;
    }
}

198. 打家劫舍 (House Robber)​

题目描述​

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 求你不触发报警装置的情况下，一夜之内能够偷窃到的最高金额。

解题思路​

状态定义 dp[i] 为直到第 i 间房屋所能偷得的最高金额。 状态转移：dp[i] = max(dp[i-2] + nums[i], dp[i-1])。

Java 代码实现​

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

279. 完全平方数 (Perfect Squares)​

题目描述​

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

解题思路​

状态转移：dp[i] = min(dp[i], dp[i - j*j] + 1)，其中 j*j <= i。

Java 代码实现​

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n); dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

322. 零钱兑换 (Coin Change)​

题目描述​

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。

解题思路​

典型的完全背包问题。 状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)。

Java 代码实现​

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

139. 单词拆分 (Word Break)​

题目描述​

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼凑出 s 则返回 true。

解题思路​

状态定义 dp[i] 表示前 i 个字符能否被拆分。 状态转移：如果 dp[j] 为真且子串 s[j...i] 在字典中，则 dp[i] 为真。

Java 代码实现​

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true; break;
                }
            }
        }
        return dp[s.length()];
    }
}

300. 最长递增子序列 (Longest Increasing Subsequence)​

题目描述​

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

解题思路​

状态定义 dp[i] 为以 nums[i] 结尾的最长自增子序列长度。 状态转移：dp[i] = max(dp[j]) + 1，满足 j < i 且 nums[j] < nums[i]。 可以用二分查找优化到 O(n log n)。

Java 代码实现​

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

152. 乘积最大子数组 (Maximum Product Subarray)​

题目描述​

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积。

解题思路​

考虑负数情况：负负得正。维护两个变量：maxProd（当前最大值）和 minProd（当前最小值）。遇到负数时，两数交换。

Java 代码实现​

class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < 0) { int tmp = max; max = min; min = tmp; }
            max = Math.max(nums[i], max * nums[i]);
            min = Math.min(nums[i], min * nums[i]);
            res = Math.max(res, max);
        }
        return res;
    }
}

416. 分割等和子集 (Partition Equal Subset Sum)​

题目描述​

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

解题思路​

等价于：从数组中选出若干数，和恰好为总和的一半（target = sum / 2）。0-1 背包问题。

Java 代码实现​

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int n : nums) {
            for (int j = target; j >= n; j--) {
                dp[j] = dp[j] || dp[j - n];
            }
        }
        return dp[target];
    }
}

32. 最长有效括号 (Longest Valid Parentheses)​

题目描述​

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解题思路​

使用栈辅助。栈内存放索引。先压入 -1 作为垫脚石。

  • 遇 (：入栈索引。
  • 遇 )：弹栈。弹栈后若栈为空，压入当前索引。否则 i - stack.peek() 即为当前有效长度。

Java 代码实现​

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') stack.push(i);
            else {
                stack.pop();
                if (stack.isEmpty()) stack.push(i);
                else res = Math.max(res, i - stack.peek());
            }
        }
        return res;
    }
}