爬楼梯

cpp
class Solution {
public:
    int climbStairs(int n) {
        if(n<=1) return n;
        vector<int>dp(n+1);
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }

        return dp[n];



    }
};

最小花费爬楼梯

cpp
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size()+1);

        dp[0]=0;
        dp[1]=0;

        for(int i=2;i<=cost.size();i++) {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }

        return dp[cost.size()];

    }
};

过河卒

cpp
#include <bits/stdc++.h>
using namespace std;
long long dp[25][25];
int x,y,n,m;
bool s[30][30];
int main()
{
   cin>>n>>m>>x>>y;
   n+=2,m+=2,y+=2,x+=2;
   dp[2][1]=1;
   s[x][y]=1;
    s[x-2][y-1]=1;
	s[x-2][y+1]=1;
	s[x+2][y-1]=1;
	s[x+2][y+1]=1;
	s[x-1][y+2]=1;
	s[x-1][y-2]=1;
	s[x+1][y+2]=1;
	s[x+1][y-2]=1;
   for(int i=2;i<=n;i++)
   {
       for(int j=2;j<=m;j++)
       {
           if(s[i][j])continue;
           dp[i][j]=dp[i][j-1]+dp[i-1][j];
       }
   }
    cout<<dp[n][m];
    return 0;
}


// 大佬题解

数字三角形

cpp
include<iostream> 
include<cstdio> 
include<cmath> 
using namespace std;  
int n;  
int a[1000][1000];  
int main()  
{       
	scanf("%d",&n);  
	for(int i=0;i<n;i++)  
	for(int j=0;j<=i;j++)  
	scanf("%d",&a[i][j]);//以上输入  
	for(int i=n-2;i>=0;i--)   
	{  
 		for(int j=0;j<=i;j++)//for循环按顺序扫描除最后一排前的所有数  
		a[i][j]+=max(a[i+1][j],a[i+1][j+1]); 
        //从左下，右下中选取大的加到现在的位置上 
    } 
    cout<<a[0][0]<<endl; 
    return 0; 
 }
 
 
 
 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
#define rint register int
inline void read(int &x)//读入优化 
{
    x=0;int w=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}
const int maxn=1000+10;
int n,a[maxn][maxn],ans; 
int main()
{
    read(n);
    for(rint i=1;i<=n;i++)
    {
        for(rint j=1;j<=i;j++)
        {
            read(a[i][j]);
            a[i][j]+=max(a[i-1][j-1],a[i-1][j]);//本题最重要的步骤 
            //a[i][j]代表从上往下到达i行j列这个点所能达到的和的最大值 
            ans=max(ans,a[i][j]);//在所有答案中找最大的（与在最底下一层找最大值是一样的）
        }
    }//边读入边计算，随手优化一下常数（其实只是懒得打for循环） 
    cout<<ans<<endl;
    return 0; 
} 


#include<stdio.h>
#include<iostream>
using namespace std;
int main(int argc, char** args) {
	int r = 0, map[1005][1005]; //r是层数, map用来存放对应的数字
	scanf("%d", &r);
	for(int i = 1;i <= r;i++) {
		for(int j = 1;j <= i;j++) {
			scanf("%d", &map[i][j]);
		}
	}
	int dp[1005][1005] = {0}, ans = 0; //dp用来存放状态, ans用来存放答案
	for(int i = 1;i <= r;i++) {
		for(int j = 1;j <= i;j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + map[i][j];
			if(dp[i][j] > ans) { //假如取到的数字和大于原先取到的
				ans = dp[i][j];
			}
		}
	}
	printf("%d", ans);
}
 
 
 
 

线段

cpp
#include <iostream>
#include <cstdio>
#define rep(i,m,n) for(int i=m;i<=n;++i)
using namespace std;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
const int MAXN = 20010;
int n;
int l[MAXN], r[MAXN], f[MAXN][2];
int main(){
    n = read();
    rep(i, 1, n) l[i] = read(), r[i] = read();
    f[1][0] = r[1] + r[1] - l[1] - 1;
    f[1][1] = r[1] - 1;
    rep(i, 2, n)
       f[i][0] = min(f[i-1][0] + abs(l[i-1] - r[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - r[i]) + r[i] - l[i] + 1),
       f[i][1] = min(f[i-1][0] + abs(l[i-1] - l[i]) + r[i] - l[i] + 1, f[i-1][1] + abs(r[i-1] - l[i]) + r[i] - l[i] + 1);
    printf("%d\n", min(f[n][0] + n - l[n], f[n][1] + n - r[n]));
    //rep(i, 1, n){ rep(j, 0, 1) printf("f[%d][%d] = %d, ", i, j, f[i][j]); puts(""); }
    return 0;
}

整数划分

cpp

// 背包问题
using namespace std;

const int N = 1e3 + 7, mod = 1e9 + 7;

int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i <= n; i ++) {
        f[i][0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
            if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
        }
    }

    cout << f[n][n] << endl

}