感觉自己做题一直没什么规划，看到什么做什么，这几天就准备系统的练习一下动态规划了，这几天都在洛谷做动态规划吧。。。。
以下问题完全是纸币问题大家族来的。。。
1.https://www.luogu.com.cn/problem/P2842
状态转移方程：dp[i] = min{dp[i-aj]+1}
#include<iostream> using namespace std; int n,w; int dp[10005],a[1005]; int main(){ cin >> n >> w; fill(dp, dp + w + 1, w + 1); dp[0] = 0; for(int i = 0;i < n;i++){ cin >> a[i]; dp[a[i]] = 1; } for(int i = 1;i <= w;i++){ for(int j = 0;j < n;j++){ if(i < a[j]) continue; if(dp[i-a[j]]!= w+1) dp[i] = min(dp[i],dp[i-a[j]]+1); } } cout << dp[w]<<endl; return 0; }2.https://www.luogu.com.cn/problem/P2840
“你是一个非常有钱的小朋友。”
这个题目求得是有多少种方案，那最后一张不一定是几，结果就是前一步所有情况，每种情况的方案数的和
所以状态转移方程就是：dp[i] = dp[i]+sum{dp[i-a[j]]}
#include<iostream> using namespace std; int n,w; int dp[10005],a[1005]; const int mod = 1e9+7; int main(){ cin >> n >> w; for(int i = 0;i < n;i++){ cin >> a[i]; } dp[0] = 1; for(int i = 1;i <= w;i++){ for(int j = 0;j < n;j++){ if(i >= a[j]){ dp[i] = (dp[i] +dp[i-a[j]])%mod; } } } cout <<dp[w] <<endl; return 0; }3.https://www.luogu.com.cn/problem/P2834
bushi?
#include<iostream> using namespace std; int n,w; int dp[10005],a[1005]; const int mod = 1e9+7; int main(){ cin >> n >> w; for(int i = 0;i < n;i++){ cin >> a[i]; } dp[0] = 1; for(int i = 0;i < n;i++){ for(int j = a[i];j <= w;j++){ dp[j] = (dp[j] + dp[j-a[i]])%mod; } } cout <<dp[w] <<endl; return 0; }我的大脑有点乱乱的了，怎么感觉又会又不会的。。。。
dp[j] = 不用当前纸币+至少用一张当前纸币
闪现力扣
今天的做题顺序是这样的
(这些题目都不太难，列列0123就能写出来状态转移方程，可以做做给自己点信心。。。。）主要是本小白做题总是会被打击啊喂，不过没关系我是打不死的小强,但是个人觉得对于刚开始学习动态规划理解这些内容是有帮助的，会感觉能想通很多细节，再慢慢的做后面的进阶题。如果直接给你一道动态规划的难题对我来说我会做的一知半解，很多细节就会觉得莫名其妙，跟着题解ac了之后后面出现类似的题还是不会做。。。。
1.70. 爬楼梯 - 力扣（LeetCode）
2.509. 斐波那契数 - 力扣（LeetCode）
3.1137. 第 N 个泰波那契数 - 力扣（LeetCode）
4.746. 使用最小花费爬楼梯 - 力扣（LeetCode）
5.198. 打家劫舍 - 力扣（LeetCode）
6.740. 删除并获得点数 - 力扣（LeetCode）
这道题可以转化为和5类似的题，就是这道题你选择n那么所有的n-1和n+1就都没有了，那么剩下的所有的n你就都可以选,现在就变成 数字->数字总和（每家谁的钱多），而且相邻的家不能打劫
class Solution { public: int deleteAndEarn(vector<int>& nums) { int maxnum = 0; for(int i : nums){ maxnum = max(i,maxnum); } vector<int> sum(maxnum+1,0); for(int i:nums){ sum[i] += i; } vector<int> dp(maxnum+1,0); dp[1] = sum[1]; for(int i = 2;i <= maxnum;i++){ dp[i] = max(dp[i-1],dp[i-2]+sum[i]); } return dp[maxnum]; } };吃饱睡足回来了
7.62. 不同路径 - 力扣（LeetCode）
这道题我开始用的是二维数组的写法，不怎么难想，然后我看到了题解中是优化为一维数组写的，遂学之。。
他是怎么将二维的f[i][j] = f[i-1][j]+f[i][j-1]变成一维的f[j] += f[j-1]的呢？
首先我们要先理解这个状态转移方程f[i]:表示的是在当前计算的这一行中，第j列有多少种走法
其实这俩式子就是一个意思
f[j] =f[j]+f[j-1]这个橙色的就是当前行的第j-1列那不就是原式的f[i][j-1]，红色的是前一行的第j列，因为现在的这一行我们还没有更新，所以这里f[j]存的是第i-1行第j列的数据，也就是二维数组中的 f[i-1][j]，OK过了！
class Solution { public: int uniquePaths(int m, int n) { vector<int> f(n,1); for(int i = 1;i < m;i++){ for(int j = 1;j < n;j++){ f[j] = f[j] + f[j-1]; } } return f[n-1]; } };在第9题又碰到了降维优化的方法
滚动数组的核心思想：如果计算当前状态只需要前面少数几行的数据，就没必要把所有行都保存下来，可以重复利用数组空间
假设你需要计算 100 行数据，每一行都依赖上一行：
计算第 1 行，需要第 0 行。
计算第 2 行，需要第 1 行。
计算第 3 行，需要第 2 行。
当你已经算出第 3 行时，还需要保留第 0 行的结果吗？
不需要了，因为接下来的计算只需要第 2 行和第 3 行附近的数据。
所以，我们可以准备两张草稿纸：
一张保存上一行。
一张计算当前行。
每算完一行，就交换两张草稿纸的角色。这样就不用准备 100 张草稿纸了。
这就是滚动数组思想。
8.64. 最小路径和 - 力扣（LeetCode）
9.63. 不同路径 II - 力扣（LeetCode）
如果当前点ij有障碍物，那么在当前这一行，第j列的走法一定是0，可以与第七题一起看，这道题目加了障碍物。
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int n = obstacleGrid.size(),m = obstacleGrid[0].size(); int f[105]; f[0] = (obstacleGrid[0][0] == 0?1:0); for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++){ if(obstacleGrid[i][j] == 1){ f[j] = 0; continue; } if(j-1 >= 0 && obstacleGrid[i][j-1] == 0){ f[j] = f[j]+f[j-1]; } } } return f[m-1]; } };10.120. 三角形最小路径和 - 力扣（LeetCode）
这道题也是二维转一维做的，这道题是自底向上来解决的，dp[j]表示在当前行第j列距离底部的最小距离，初始化是使用的数组的最后一行对dp进行初始化
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int n = triangle.size(); vector<int> dp = triangle[n-1]; for(int i = n-2;i >= 0;i--){ for(int j = 0;j <= i;j++){ dp[j] = min(dp[j],dp[j+1])+triangle[i][j]; } } return dp[0]; } };
