动态规划概述
动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。它是一种最优化原理，利用各阶段之间的关系逐个求解，最终求得全局最优解。在设计动态规划算法时，需要确认原问题与子问题、动态规划状态、边界状态结值、状态转移方程等关键要速。
动态规划原理
- 确认原问题与子问题
- 确认状态
- 确认边界状态的值
- 确定状态转移方程
例1：爬楼梯（LeetCode70-简单）
题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
思想：
递归回溯法：
上一步要不是走1步，要不走2步；递归即可！
class Solution {
public:int climbStairs(int n) {if(n==1 || n==2){return n;}return climbStairs(n-1)+class(n-2);}
};
但这样做会超时！！！！因为我们重复算了大量的值！
动态规划：
1.确认原问题与子问题：
原问题是求N阶台阶的所有走法；子问题是求1..2....n-1阶台阶的走法
2.确认状态：
第i个状态就是i阶台阶的所有走法数量
3.确认边界状态的值：
边界状态为1阶和2阶台阶的走法，dp[1]=1,dp[2]=2
4.确定状态转移方程：
dp[i]=dp[i-1]+dp[i-2]
代码：
class Solution {
public:int climbStairs(int n) {//注意：n+3是为了防止传进来0时运行出错vector<int> dp(n+3,0);dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};
例2：打家劫舍（LeetCode 198-简单）
题目：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
思想：
1.原问题与子问题：
原问题是求n个房间的最优解，子问题是求前1...2....n-1个房间的最优解
2.状态：
dp[i]表示前i个房间的最优解
3.确认边界值：
dp[1]=nums[0];
dp[2]= max(nums[0] , nums[1] )
4.转移方程：
dp[i]=max(dp[i-1] , dp[i-2]+nums[i]) i>=3;
代码：
class Solution {
public:int rob(vector<int>& nums) {if(nums.size() ==0 ){return 0;}if(nums.size() ==1){return nums[0];}vector<int> dp(nums.size(),0);dp[0]=nums[0];dp[1]=std::max(nums[0],nums[1]);for(int i=2;i<nums.size();i++){dp[i]=std::max(nums[i]+dp[i-2] , dp[i-1]);}return dp[nums.size()-1];}};
例3：最大子段和（LeetCode 53-简单）
题目：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例：
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思想：
1.原问题与子问题：
原问题是n个数中连续子段最大和，子问题是以 1..2..n-1为结尾的子段的和的最大值
2.状态：
dp[i]表示以i为结尾的连续字串中和的最大值
3.边界条件：
dp[0]=nums[0]
dp[1]=max(nums[1] , nums[1]+dp[0] )
4.转移方程：
dp[i]=max( dp[i-1] + nums[i] , nums[i])
代码：
class Solution {
public:int maxSubArray(vector<int>& nums) {int result=0;vector<int> dp(nums.size(),0);dp[0]=nums[0];result=dp[0];for(int i=1;i<nums.size();i++){dp[i]=std::max(dp[i-1]+nums[i],nums[i]);if(dp[i]>result){result=dp[i];}}return result;}
};
例4：找零钱（LeetCode 322-中等）
题目;
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例：
输入: coins =[1, 2, 5], amount =11输出:3解释: 11 = 5 + 5 + 1
输入: coins =[2], amount =3输出: -1
思想：
代码: