互联网平台推广是什么意思,seo网站托管,做亚马逊外国网站需要语言好吗,厦门网络推广公司动态规划理论基础
如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的。
动态规划解题步骤#xff1a;
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定…动态规划理论基础
如果某一问题有很多重叠子问题使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的。
动态规划解题步骤
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
509. 斐波那契数
确定dp数组以及下标的含义 dp[i]的定义为第i个数的斐波那契数值是dp[i]确定递推公式 dp[i] dp[i - 1] dp[i - 2]dp数组如何初始化 dp[0] 0; dp[1] 1;确定遍历顺序 遍历可以从2开始从前向后遍历举例检查dp数组
/*** param {number} n* return {number}*/
var fib function (n) {let dp [0, 1]for (let i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2]}console.log(dp)return dp[n]
};70. 爬楼梯
可以多举几个例子就可以发现其规律。
爬楼梯问题类似于斐波那契数唯一的区别是dp[0] 的值是1.因为爬2阶台阶时有两种方法且dp[2] dp[0] dp[1]。
/*** param {number} n* return {number}*/
var climbStairs function (n) {let dp [1, 1]for (let i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2]}return dp[n]
};746. 使用最小花费爬楼梯
动态规划五部曲
dp[i]的定义到达第i台阶所花费的最少体力为dp[i]。递推公式用两个途径可以得到dp[i]一个是dp[i-1] 一个是dp[i-2]。dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);dp初始化只初始化dp[0]和dp[1]就够了其他的最终都是dp[0]dp[1]推出。到达 第 0 个台阶是不花费的但从 第0 个台阶 往上跳的话需要花费 cost[0]。所以初始化 dp[0] 0dp[1] 0。遍历顺序最后遍历到等于cost的长度才到达了顶部而不是cost.length - 1。打印检查dp数组
/*** param {number[]} cost* return {number}*/
var minCostClimbingStairs function (cost) {let dp [0, 0]for (let i 2; i cost.length; i) {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])}return dp[cost.length]
};
