动态规划基础1
dp就是动态规划（废话）
我们先来看一道最为基础的dp题：
三角形最小路径和（leetcode)
给定一个三角形
triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标
i，那么下一步可以移动到下一行的下标i或i + 1。示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示：23 46 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。示例 2：
输入：triangle = [[-10]] 输出：-10提示：
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
这题可以搜索吗？
不可以，因为如果搜索的话。。。。。算了你去问问时间复杂度吧
所以我们来用动态规划来解决此类问题，但是dp的做题步骤是什么？先不说做题步骤我们等会儿细讲。
思路：
用dp[i][j]来表示从三角形最顶端（triangle[0][0]）走到triangle(i,j)的最小权值和；
而dp[n][n]可以拆成若干个子问题，即若干个dp[i][j]
而dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+triangle[i][j];
dp[0][0]=triangle[0][0];(显然）
那么我们可以得到边界条件，动态转移方程：
dp[0][0]=triangle[0][0];
dp[i][j]=min(dp[i-1][j-1]，dp[i-1][j])+triangle[i][j];
得到这两个东西后就可以很简单的求解了
class Solution {
public:int minimumTotal(vector<vector<int>>& a) {int n=a.size(),ans=INT_MAX;vector<vector<int>> dp(n,vector<int> (n,INT_MAX));dp[0][0]=a[0][0];for(int i=1;i<n;i++){//dpdp[i][0]=dp[i-1][0]+a[i][0];dp[i][i]=dp[i-1][i-1]+a[i][i];for(int j=1;j<i;j++){dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+a[i][j];}}for(int i=0;i<n;i++) ans=min(ans,dp[n-1][i]); return ans;}
};(将triangle改为了a)
打家劫舍（leetcode)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
思路：
对于第 k (k>2) 间房屋，有两个选项：
偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
设dp[i]为前 i 间房屋能偷窃到的最高总金额，则有如下动态转移方程：
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
边界条件为：dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])
最终的答案为：dp[n-1]
class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int length = nums.length;if (length == 1) {return nums[0];}int[] dp = new int[length];dp[0] = nums[0];dp[1] = max(nums[0], nums[1]);for (int i = 2; i < length; i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[length - 1];}
}P1164 小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
题目描述
不过 uim 由于买了一些书，口袋里只剩 M 元 (M <= 10000)
餐馆虽低端，但是菜品种类不少，有 N 种 (N <=100)，第 i 种卖 ai 元 (ai <= 1000)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”的原则，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 1 秒。
输入格式
第一行是两个数字，表示 N 和 M。
第二行起 N个正数 ai（可以有相同的数字，每个数字均在 1000$以内）。
## 输出格式
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
样例 #1
样例输入 #1
```
4 4
1 1 2 2
```### 样例输出 #1
```
3
```## 提示
2020.8.29，增添一组 hack 数据 by @yummy
思路：
裸的dp，按照常规套路，令dp[i][j]为前i道菜可以花完j元的总方案数 （j=1,2,.....,m-1,m)
在设a[i]是第i道菜的价格。则可以得到状态转移方程：
if(j==a[i]) dp[i][j]=dp[i-1][j]+1;
if(j>a[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];
if(j<a[i]) dp[i][j]=dp[i-1][j];
那么第二个式子是怎么推的呢？
if(j>a[i])dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]的推导思路：
推导上式可以转成推导：dp[j]+=dp[j-a[i]
第一种可行的方案是买当前第i道菜品，这个时候前i-1个物品所需要的钱应该是j-a[i], 也就是说前i个物品中所有能凑出j-a[i]元的方案再加上当前这道菜品，就可以变成前i个物品所需的钱为j的方案数。即f[i][j]+=f[i-1][j-a[i]]
说的简单一些，这三个方程，每一个都是在吃与不吃之间抉择。若钱充足，办法总数就等于吃这道菜的办法数与不吃这道菜的办法数之和；若不充足，办法总数就只能承袭吃前i-1道菜的办法总数。依次递推，在最后，我们只要输出f[n][m]的值即可。
#include<cstdio>
long long n,m,a[110],dp[110][100001];
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(j==a[i]) dp[i][j]=dp[i-1][j]+1;if(j>a[i]) dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];if(j<a[i]) dp[i][j]=dp[i-1][j];}}printf("%d",dp[n][m]);
}其实小A点菜这题就是典型的背包问题01，（01背包）
对于01背包我们要记住:dp[i]+=dp[j-v[i]]
总结：dp五步法
1.构造问题
2.拆解问题（将原问题拆解成若干个子问题）
3.求解简单子问题
4.通过已知的子问题来推导原问题（构造状态转移方程）
5.判断复杂度（会不会T)