经典算法思想2-动态规划

动态规划（dynamic programing），通常用于求解具有某种最优性质的问题。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是动态规划问题的解答，通常依赖子问题的解，也就是说，子问题之间并非独立。

动态规划的题目类型

1、计数：
有多少种方式走到右下角，如青蛙跳台阶。
有多少种方法选出k个数使得和为Sum，如硬币组合问题。
2、最大最小值：
从左上角走到右下角路径的最大数字和
最长公共子序列。
3、存在性：
取石子游戏，先手是否必胜
能不能选出k个数使得和是Sum

动态规划解题基本步骤

1. 确定状态
   简单的说，就是解动态规划时需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么，有时也可只用两个状态变量（dp0,dp1）表示。具体分为下面两个步骤：
   -------研究最优策略的最后一步
   -------化为子问题
2. 状态转移方程
   根据子问题定义直接得到
3. 初始条件和边界情况
   初始条件一般都是a[0]、a[1]这种
   边界条件主要是看数组的边界，数组越不越界
4. 计算顺序
   利用之前的计算结果

动态规划问题实例

1. 硬币兑换问题
状态方程：

金额为X时，需要的最小的硬币数量的状态方程

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp=[float('inf')] * (amount+1)
        dp[0]=0

        for i in range(1,amount+1):
            for coin in coins:
                ## 第一个条件防止下标越界；第二个条件防止inf 越界
                if i-coin>=0 and dp[i-coin] != float('inf'):
                    dp[i]=min(dp[i-coin]+1,dp[i])
        
        return -1 if dp[amount]==float('inf') else dp[amount]

2. 按摩师问题
https://leetcode-cn.com/problems/the-masseuse-lcci/
转态方程：

class Solution:
    def massage(self, nums: List[int]) -> int:
        if len(nums)==0:
            return 0
        dp0 = 0
        dp1 = nums[0]
        for i in range(1,len(nums)):
            tdp0 = max(dp0,dp1) # 计算 dp[i][0]
            tdp1 = dp0 + nums[i] # 计算 dp[i][1]
            dp0,dp1 = tdp0,tdp1
        
        return max(dp0,dp1)

---

参考：

https://www.cnblogs.com/xsyfl/p/6926269.html
https://blog.csdn.net/weixin_44550963/article/details/107282087