动态规划——力扣刷题总结

class Solution {
public:
    int fn[46];
    int climbStairs(int n) {
        fn[1]=1;
        fn[2]=2;
        for(int i=3;i<=n;i++)
        {
            fn[i]=fn[i-1]+fn[i-2];
        }
        return fn[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxSubArray(vector& nums ) {
        int n=nums.size();
        int sum=0;
        int ans=-999999999;
        for(int i=0;i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

1706 球会落到何处
对每一层情况进行分析，当前层的位置是有上一层的挡板情况确定，分析清楚什么时候右移一个位置，什么时候左移，什么时候卡在挡板处即可
代码：

class Solution {
public:
    vector findBall(vector>& grid) {
        int col=grid[0].size();
        int row=grid.size();
        vectorans(col,0);
        for(int i=0;i=0&&grid[i][ans[j]-1]!=1)
            {
                ans[j]--;
            }
            else{
                ans[j]=-1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1420 生成数组
设方法数为$f(n,s,j)s$表示search_cost,n表示第几个数，j表示取何值。
$$f(n,s,j)=f(n-1,s,j)\ast j+\sum _{i=1}^{x}f(n-1,s-1,s(s<j)）$$
代码：

class Solution {
private:
int mod=1000000007;
int f[51][51][1000];
int ans=0;
public:
    int numOfArrays(int n, int m, int k) {
        for(int i=1;i<=m;i++)
        {
            f[1][1][i]=1;
        }
        for(int i=2;i<=n;i++)
        for(int s=1;s<=k&&s<=i;s++)
        for(int j=1;j<=m;j++)
        {
            f[i][s][j]=(long long)f[i-1][s][j]*j%mod;
            for(int temp=1;temp