网站更改关键词/河南seo技术教程

• 动态规划是算法设计中一种方法
• 它讲一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题
• 解决实例-斐波那契数列问题
  

leetcode:70 爬楼梯

• 解题思路
  • 爬到第n阶可以在第n-1阶爬1个台阶，或在第n-2阶爬2个阶梯
  • F(n) = F(n-1)+F(n-2)
  • 使用动态规划
• 解题步骤
  • 定义子问题：F(n) = F(n-1)+F(n-2)
  • 反复执行：从2循环到n，执行上述公式

代码

// n：第n阶台阶
var climbStairs = function(n) {if (n < 2) return 1;let dp0 = 1;let dp1 = 1;for (let i = 2; i <= n; i++) {const temp = dp0;dp0 = dp1;dp1 = dp1 + temp;}return dp1;
}

leetcode:198 打家劫舍

• 解题思路
  • f(k) = 从前k个房屋中能偷窃到的最大数额
  • Ak = 第k个房屋的钱数
  • f(k) = max(f(k - 2) + Ak, f(k -1))
• 解题步骤
  • 定义子问题：f(k) = max(f(k - 2) + Ak, f(k -1))
  • 反复执行：从2循环到n，执行上述公式

// nums：[]number 数组，代码多个房屋，number为每个房屋的钱数
var rob = function(nums) {if (nums.length === 0) return 0;let dp0 = 0; // 第0间房不存在 0元let dp1 = nums[0]； // 第1间房的的钱数for(let i = 2; i <= nums.length: i++) {// 从第2间房开始算const dp2 = Math.max(dp0 + nums[i - 1], dp1);dp0 = dp1;dp1 = dp2;}return dp1
}