当前位置：首页 > news >正文

【学习笔记12.25】动态规划入门

news 来源：原创 2024/5/2 11:07:43

动态规划

看完本文你可以解决的题目有：

题目	题型
509. 斐波那契数 - 力扣（LeetCode）	简单动态规划
70. 爬楼梯 - 力扣（LeetCode）	简单动态规划

动态规划问题的一般形式就是求最值。如果某一问题有很多重叠子问题，使用动态规划就是最佳的。

确定dp数组以及下标的含义。
确定递推公式。
dp数组如何初始化。
确定遍历顺序。
举例推导dp数组。

一般来说，函数的参数就是状态，函数的返回值就是要求我们计算的量。

解题模板：

# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
    for 选择 in 所有可能的选择:
        # 此时的状态已经因为做了选择而改变
        result = 求最值(result, dp(状态1, 状态2, ...))
    return result

# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

LeetCode

leetcode 509

使用五个步骤对题目进行分析，可以得到斐波那契数列的第n个数。

class Solution {
    static int N = 31;
    public int fib(int n) {
        //1. fib数列的第i个数就是dp[i]。
        int [] dp = new int [N];
        //3. 数组初始化
        dp[0] = 0;
        dp[1] = 1;
        //4. 遍历顺序是从前往后，因为后面的值由前面的推导而来。
        for(int i = 2;i <= n;i++){
            //2. 递推公式
            dp[i] = dp[i - 1] + dp[ i - 2];
        }
        //5. 举例推导dp数组
        // 当n为3时， dp={0, 1, 1, 2}; 
        return dp[n];
    }
}

leetcode 70

通过规律发现，该问题也是重叠子问题。所以使用动态规划，再通过五步法解题。

class Solution {
    //4节
        // 1. (1 + 1 + 1)  + 1
        // 2. (1 + 2) + 1
        // 3. (2 + 1) + 1
        // 4. (1 + 1) + 2
        // 5. (2) + 2
    public int climbStairs(int n) {
        if(n == 1) return 1;
        //1. dp数组含义：i阶楼梯，有dp[i]种不同的方法。
            // 1节-1种方法
            // 2节-2种方法
            // 3节-3种方法
            // 4节-5种方法
        int [] dp = new int [n + 1];
        //3. dp数组初始化
        // dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        //4. 从前往后遍历。
        for(int i = 3;i <= n;i++){
            //2. 递推公式
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        //5. n = 4 , dp[3] = 3,dp[4] = 5.
        return dp[n];
    }
}