洛谷 P.1359
输入说明 ：
3
5 （1->2) 15 (1->3)
7 (2 -> 3)
#include#include#includeusing namespace std;vector dp(201);int main(){int n ;cin>>n;vector> ori(201,vector(201));for(int i = 1; i < n;i++ ){for(int j = i + 1; j <= n;j++){cin>>ori[i][j];}dp[i] = INT_MAX;}for(int i = n - 1;i > 0;i--){for(int j = i + 1; j <= n;j++ ){dp[i] = min(dp[i] , dp[j] + ori[i][j]);}}cout<
状态转移关系 ： 我们要用i把n上流的中转站从大到小跑一遍。我们先记录中转站2到中转站3的最小价钱，我们要用jj跑一遍中转站2下流的所有中转站，记录ori[i][j]+dp[j]的最小价钱,记录到dp[i]里面。
细节 ： 因为dp[i}是每次min来的，但dp各项初始化为0，因此我们要让除了最后一个中转站外设为INT_MAX（用头文件#include)
洛谷 P.1060
01背包问题！
无优化代码
for(int i=1;i<=n;i++){ for(int c=0;c<=m;c++) { f[i][c]=f[i-1][c]; if(c>=w[i]) f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]); }}
一维数组优化 ：
for(int i=1;i<=n;i++){ for(int c=m;c>=0;c--) { if(c>=w[i]) f[c]=max(f[c],f[c-w[i]]+v[i]); }}
#includeusing namespace std;int w[30],v[30],dp[30][100000];int main(){int m, n;//m为总价，n为数量cin>>m>>n; for(int i = 1;i <=n;i++){ cin>>v[i]>>w[i]; w[i] *= v[i];//w[i]变为总收获 } for(int i = 1;i <= n;i++ ){ for(int j = 0;j <= m;j++){ dp[i][j] = dp[i - 1][j]; if(j >= v[i]){ dp[i][j] = max(dp[i][j] , dp[i - 1][j - v[i]] + w[i]); } } } cout<
//优化版#includeusing namespace std;int w[30],v[30],dp[100000];int main(){int m, n;//m为总价，n为数量cin>>m>>n; for(int i = 1;i <= n;i++){ cin>>v[i]>>w[i]; w[i] *= v[i];//w[i]变为总收获 } for(int i = 1;i <= n;i++ ){ for(int j = m;j >= v[i];j--){ dp[j] = max(dp[j] , dp[j - v[i]] + w[i]); } } cout<
洛谷P.1802
与上题相似 直接上代码‘
#include #include #include using namespace std;int lose[1001],win[1001],use[1001];long long f[1001][1001];int main(){ int n,x; cin>>n>>x; for (int i=1;i<=n;i++) cin>>lose[i]>>win[i]>>use[i]; for (int i=1;i<=n;i++) for (int j=0;j<=x;j++) if (j>=use[i]) f[i][j]=max(f[i-1][j-use[i]]+win[i],f[i-1][j]+lose[i]); else f[i][j]=f[i-1][j]+lose[i]; cout<
#include #include using namespace std;int dp[1100];int win[1100],lose[1100],use[1100];int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%d%d",lose+i,win+i,use+i); for(int i=1;i<=n;i++) { for(int j=m;j>=use[i];j--) dp[j]=max(dp[j]+lose[i],dp[j-use[i]]+win[i]); for(int j=use[i]-1;j>=0;j--) dp[j]+=lose[i];//其余情况不是0而要加lose[i] } printf("%lld",5ll*dp[m]);}
洛谷P.1049
看似与01背包不同，但我们可以看作它价值与容量相等（v[i] = w[i])，即与1060一致
状态转移关系 ： dp（x）为在x的最大容积下（对应1060的最大价格）最多能装下多少容积（对应1060最多价值），最后将m - dp（m）即为最小剩余容量 。。
#includeusing namespace std;int a[31],dp[20001];int main(){int m , n;cin>>m>>n;for(int i = 1;i <= n;i++){cin>>a[i];}for(int i = 1;i <=n;i++){for(int j = m; j >= a[i];j--){dp[j] = max(dp[j] , dp[j -a[i]] + a[i]); }}cout<
来题几何
LeetCode.221
设dp（i，j）为以（i，j）为右下角的正方形边长的最大值
边界情况 ：i = 0或 j = 0并且matrix[i][j]==1时dp[i][j]为1（无法向左上角延申）
动态转移关系 ：dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;（取决于左边，坐上，上面）最小的dp（画图理解，这种题主要背）
class Solution {public: int maximalSquare(vector>& matrix) { int maxSide = 0; int rows = matrix.size(), columns = matrix[0].size(); vector> dp(rows, vector(columns)); for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (matrix[i][j] == '1') { if (i == 0 || j == 0) { dp[i][j] = 1; } else { dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } maxSide = max(maxSide, dp[i][j]); } } } int maxSquare = maxSide * maxSide; return maxSquare; }};
LeetCode : 118
弄成二维数组看更直观 ：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
很容易看出边界情况 ：dp[m][0] = dp[m][m] = 1，
状态转移关系 ： dp[m][n] = dp[m - 1][n - 1] + dp[m - 1][n]，&&n > 0&&n < m
class Solution {public: vector> generate(int numRows) { vector> dp(numRows); for(int i = 0; i < numRows;i++ ){ dp[i].resize(i + 1);//每行变成i + 1列 dp[i][0] = 1; dp[i][i] = 1; for(int j = 1;j < i;j++){ dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } } return dp; }};
LeetCode : 119
水题放松下，和118一致
class Solution {public: vector getRow(int rowIndex) { vector> dp(rowIndex + 1); for(int i = 0; i < rowIndex + 1;i++ ){ dp[i].resize(i + 1);//每行变成i + 1列 dp[i][0] = 1; dp[i][i] = 1; for(int j = 1;j < i;j++){ dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } } return dp[rowIndex]; }};