动态规划的常用状态转移方程总结

03-11 1155阅读

动态规划的常用状态转移方程总结

文章目录

动态规划的常用状态转移方程总结

1.斐波那契数列

1. 斐波那契数列定义
2. 动态规划方程
2.爬楼梯问题

1. 爬楼梯问题定义
2.动态规划方程
3.背包问题

1. 背包问题定义
2. 动态规划方程
4.最长递增子序列

1. 最长递增子序列定义
2. 动态规划方程
5.最大子数组和

1. 最大子数组和定义
2. 动态规划方程
6.最长公共子序列

1. 最长公共子序列定义
2. 动态规划方程
7.编辑距离

1. 编辑距离定义
2. 动态规划方程
8.打家劫舍

1. 打家劫舍问题定义
2. 动态规划方程
9.最大正方形

1. 最大正方形定义

2. 动态规划方程

1.斐波那契数列

1. 斐波那契数列定义

斐波那契数列是一个经典的数学数列，其中每个数字是前两个数字的和。通常，斐波那契数列的前几个数字是：1, 1, 2, 3, 5, 8, 13, 21, …

（图片来源网络，侵删）

2. 动态规划方程

动态规划的转移方程为 dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 表示第 i 个斐波那契数。

// 定义一个函数，接受斐波那契数列的序号作为参数
function fibonacci(n) {
    // 初始化一个数组dp，用于存储斐波那契数列的值
    const dp = [];
    // 初始条件：第0个和第1个斐波那契数都为1
    dp[0] = dp[1] = 1;
    // 通过动态规划的转移方程计算每个斐波那契数
    for (let i = 2; i 
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 返回第n个斐波那契数
    return dp[n];
}
// 测试例子
const n = 5;
const result = fibonacci(n);
console.log(`第${n}个斐波那契数为：${result}`); 
//第5个斐波那契数为：8 数组[5]  1 1 2 3 5 8

    // 初始化一个数组dp，用于存储到达每一级楼梯的方法数
    const dp = [];
    // 初始条件：爬到第0级和第1级楼梯的方法数都为1
    dp[0] = dp[1] = 1;
    // 通过动态规划的转移方程计算每一级楼梯的方法数
    for (let i = 2; i 
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 返回爬到第n级楼梯的方法数
    return dp[n];
}
// 测试例子
const n = 4;
const result = climbStairs(n);
console.log(`爬到第${n}级楼梯的方法数为：${result}`);  
//爬到第4级楼梯的方法数为：5
当 n=4 时，输出结果是 5，表示爬到第 4 级楼梯有 5 种不同的方式。这包括：
1 步 + 1 步 + 1 步 + 1 步
2 步 + 1 步 + 1 步
1 步 + 2 步 + 1 步
1 步 + 1 步 + 2 步
2 步 + 2 步

    const n = weights.length; // 物品的数量
    // 初始化一个二维数组dp，表示在前i个物品中选择总重量不超过j的最大价值
    const dp = new Array(n + 1).fill(0).map(() = new Array(capacity + 1).fill(0));
    // 动态规划，计算每个子问题的最优解
    for (let i = 1; i 
        for (let j = 1; j 
            // 当前物品的重量
            const currentWeight = weights[i - 1];
            // 当前物品的价值
            const currentValue = values[i - 1];
            // 如果当前物品的重量小于等于背包的容量
            if (currentWeight 
                // 选择当前物品或不选择当前物品，取较大的价值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - currentWeight] + currentValue);
            } else {
                // 如果当前物品的重量大于背包的容量，则不能选择当前物品
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 返回在前n个物品中选择总重量不超过capacity的最大价值
    return dp[n][capacity];
}
// 测试例子
const weights = [2, 1, 3];
const values = [4, 2, 3];
const capacity = 4;
const result = knapsackProblem(weights, values, capacity);
console.log(`在给定容量为${capacity}的背包中，能够获得的最大价值为：${result}`);  
//在给定容量为4的背包中，能够获得的最大价值为：6

    const n = nums.length; // 数组的长度
    // 初始化一个数组dp，表示以第i个元素结尾的最长递增子序列的长度
    const dp = new Array(n).fill(1);
    // 动态规划，计算每个子问题的最优解
    for (let i = 1; i

VPS购买请点击我