【LeetCode】跳水板

题目要求

思路

这道题的归类是记忆化搜索，我开始看到这题马上就想打一个DP，解完以后看了看题解，发现了一种好的思路。

用这种思路，我在排除两种特例（即 k = = 0 k==0 k==0和 s h o r t e r = = l o n g e r shorter==longer shorter==longer）之后，定义一个长度为 k + 1 k+1 k+1的vector，利用式子 n u m s [ i ] + = k ∗ s h o r t e r + i ∗ d i f f e r nums[i] += k*shorter + i*differ nums[i]+=k∗shorter+i∗differ，循环一遍就能达到 O ( n ) O(n) O(n)。

提交代码

class Solution {
public:
    vector divingBoard(int shorter, int longer, int k) {
        if (k == 0) {
            return vector {};
        }
        if (shorter == longer) {
            return vector {shorter*k};
        }
        vector nums(k+1);
        int differ = longer-shorter;
        for (int i = 0; i