T1

题目描述

走台阶，一次上1级或2级，台阶个数不超过36

输入描述

台阶个数

输出描述

方法总数，不合法输出0

示例1

样例输入

16

样例输出

1597

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n;
int f[40];

int main() {
    cin >> n;

    f[1] = 1, f[2] = 2;
    for (int i = 3; i <= n; i ++ )
        f[i] = f[i - 1] + f[i - 2];

    cout << f[n];

    return 0;
}

T2

题目描述

一条街道房子彼此相邻，现在这条街要拆迁，要按户分新房子，求总共最少需要多少新房子
规则1：每户至少分一套新房子
规则2：相邻的两户，人数多的家庭分的新房子要比人数少的家庭分的新房子多
规则3：人数相同的家庭分的房子数可以不同，不管他们是否相邻

示例1

样例输入

3 2 4

样例输出

5

说明

3户人分的房子数分别是2 1 2，总数至少为5

示例2

样例输入

4 1 3 3 3

样例输出

7

说明

5户人分的房子数分别是2 1 2 1 1，总数至少为7

C++ 代码

class Solution {
public:
    /**
     * 
     * @param person int整型一维数组 
     * @param personLen int person数组长度
     * @return int整型
     */
    vector<int> f;

    int house(int* person, int personLen) {
        // write code here
        f = vector<int>(personLen, 1);

        for (int i = 1; i < personLen; i ++ )
            if (person[i] > person[i - 1])
                f[i] = f[i - 1] + 1;

        for (int i = personLen - 2; i >= 0; i -- )
            if (person[i] > person[i + 1] && f[i] <= f[i + 1])
                f[i] = f[i + 1] + 1;

        int ret = 0;

        for (int i = 0; i < personLen; i ++ ) ret += f[i];

        return ret;
    }
};