动态规划问题
一、动态规划
1、核心思想
将问题划分为若干个子问题，并在计算子问题的基础上，逐步构建出原问题的解
2、解题步骤
- 定义状态：将原问题划分为若干个子问题，定义状态表示子问题的解，通常使用一个数组或者矩阵来表示
- 确定状态转移方程：在计算子问题的基础上，逐步构建出原问题的解；这个过程通常使用“状态转移方程”来描述，表示从一个状态转移到另一个状态的转移规则
- 初始化状态
- 计算原问题的解（最终答案）
- 通过计算状态之间的转移，最终计算出原问题的解
- 通常使用递归或者迭代（循环）的方式计算
二、斐波那契数列
1、核心思想
从第二个数开始，每一个斐波那契数都是它前面两个斐波那契数之和
2、代码实现
1、递归的方法
function fib(n: number): number {// 0 1 1 2 3 5 8 13 21 34 55if(n <= 1) return nreturn fib(n - 1) + fib(n - 2)
}
console.log(fib(10)) // 552、记忆化搜索
function fib(n: number, memo: number[] = []): number {if(n <= 1) return n// 求n 的值，直接从memo 中取if(memo[n]) {return memo[n]}// 如果memo 中没有这个位置的值时，再去计算const res = fib(n - 1, memo) + fib(n - 1, memo)memo[n] = resreturn res
}3、动态规划
function fib(n: number): number {// 1.定义状态// dp 保留斐波那契数列中每一个位置对应的值（状态）// dp[x]表示的就是x 位置对应的值// 2.状态转移方程：dp[i] = dp[i-1] + dp[i-2]// 状态转移方程一般情况都是写在循环中// 3.设置初始化状态：dp[0]/dp[1]初始化状态// 4.计算最终的结果// 1.定义状态// 2.初始化状态const dp: number[] = []dp[0] = 0dp[1] = 1// 3.状态转移方程for(let i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]} //4.最终结果return dp[n]
}4、状态压缩
function fib(n: number): number {if(n <= 1) return n// 1.定义状态// 2.初始化状态let prev = 0let cur = 1// 3.状态转移方程for(let i = 2; i <= n; i++) {const newValue = prev + curprev = cur cur = newValue} //4.最终结果return cur
}三、跳台阶（爬楼梯）
1、问题描述
一共有n 阶台阶，每次可以跳1 或 2阶台阶，问有多少种不同的跳法
2、核心思想
到达第n 阶台阶中能由第n - 1阶或第n - 2阶台阶跳上来
3、代码实现
1、动态规划
function jump(n: number): number {const dp: number[] = [] dp[0] = 1dp[1] = 1for(let i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2]}return dp[n]
} 2、状态压缩
function jump(n: number): number {let prev = 1let cur = 1for(let i = 2; i <= n; i++) {const newValue = prev + curprev = curcur = newVal}return cur
} 四、买卖股票的最佳时机
1、问题描述
给定一组股票数据，选择在某一天买入这只股票，并选择在未来的某一个不同的日子卖出这只股票，计算能获取的最大利润
2、代码实现
1、动态规划
// maxProfit([7,1,5,3,6,0,4]) -> 5
function maxProfit(prices: number[]): number {const n = prices.lengthif(n <= 1) return 0const dp: number[] = []dp[0] = 0for(let i = 1; i < n; i++) {dp[i] = Math.max(prices[i] - minPrice, dp[i - 1])minPrice = Math.min(prices[i], minPrice)}return dp[n-1]
}2、状态压缩
function maxProfit(prices: number[]): number {const n = prices.lengthif(n <= 1) return 0let preValue = 0let minPrice = prices[0]for(let i = 1; i < n; i++) {preValue = Math.max(prices[i] - minPrice, preValue)minPrice = Math.min(prices[i], minPrice)}return preValue
} 五、最大子数组和
1、问题描述
在一个整数数组nums，找出一个具有最大和的连续子数组，（子数组最少包含一个元素），返回其最大和
例如：
输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：[4, -1, 2, 1]
2、代码实现
1、动态规划
function maxArray(nums: number[]): number {const n = nums.lengthconst dp: number[] = []dp[0] = nums[0]for(let i = 1; i < n; i++) {dp[i] = Math.max(nums[i], nums[i] + dp[i - 1])}return Math.max(...dp)
}2、状态压缩
function maxArray(nums: number[]): number {const n = nums.lengthlet preValue = dp[0]let max = preValuefor(let i = 1; i < n; i++) {preValue = Math.max(nums[i], nums[i] + preValue)max = Math.max(preValue, max)}return max
}