动态规划（DP）

输入说明 ：

3

5 （1->2) 15 (1->3)

7 (2 -> 3)

#include
#include
#include
using 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]);
    }
}
 
#include
using 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< 
//优化版
#include
using 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）即为最小剩余容量 。。
 
#include
using 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];
    }
};