一维动态规划

509. 斐波那契数

int *dp;

// 自顶向下记忆化搜索，时间复杂度O（n）
int recursive(int n) {
    if (n == 0)return 0;
    if (n == 1) return 1;
    // 若之前计算过就直接返回
    if (dp[n] != -1) return dp[n];
    dp[n] = recursive(n - 2) + recursive(n - 1);
    return dp[n];
}

int fib(int n) {
    dp = (int *) malloc(sizeof(int) * (n + 1));
    memset(dp, -1, sizeof(int) * (n + 1));
    return recursive(n);
}

// 自下而上，时间复杂度O（n）
int fib(int n) {
    int dp[31];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        // 状态转移方程
        dp[i] = dp[i - 2] + dp[i - 1];
    return dp[n];
}

// 状态压缩，时间复杂度O（n）
int fib(int n) {
    if (n < 2) return n;
    int left = 0;
    int mid = 1;
    int right;
    
    for (int i = 2; i <= n; ++i) {
        right = left + mid;
        left = mid;
        mid = right;
    }

    return right;
}

// todo 矩阵快速幂，时间复杂度O（logn）

// 代入通项公式
int fib(int n) {
    double sqrt5 = sqrt(5);
    double fibN = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
    // 四舍五入成正数
    return round(fibN / sqrt5);
}

// 打表

983. 最低票价

// 每种方案对应的通行天数
int durations[3] = {1, 7, 30};

int min(int a, int b) {
    return a > b ? b : a;
}

// 返回从第day[i]天开始往后的行程全部完成所需的最小花费
int recursive(int *days, int daysSize, int *costs, int curIndex) {
    if (curIndex == daysSize) return 0;
    int res = 0x7fffffff;
    // 一共三种方案
    for (int i = 0; i < 3; ++i) {
        // day[index]为下一个需要买票的日子
        int index = curIndex;
        // 可以连续通行的最后一天的后一天
        int nextDay = days[index] + durations[i];
        while (index < daysSize && days[index] < nextDay)
            index++;
        // 记录最小值
        res = min(res, costs[i] + recursive(days, daysSize, costs, index));
    }
    return res;
}

// 暴力法超时，时间复杂度O（3^n）
int mincostTickets(int *days, int daysSize, int *costs, int costsSize) {
    return recursive(days, daysSize, costs, 0);
}

// 每种方案对应的通行天数
int durations[3] = {1, 7, 30};
int *dp;

int min(int a, int b) {
    return a > b ? b : a;
}

// 返回从第day[i]天开始往后的行程全部完成所需的最小花费
int recursive(int *days, int daysSize, int *costs, int curIndex) {
    if (curIndex == daysSize) return 0;
    if (dp[curIndex] != 0x7fffffff) return dp[curIndex];
    int res = 0x7fffffff;
    // 一共三种方案
    for (int i = 0; i < 3; ++i) {
        // day[index]为下一个需要买票的日子
        int index = curIndex;
        // 可以连续通行的最后一天的后一天
        int nextDay = days[index] + durations[i];
        while (index < daysSize && days[index] < nextDay)
            index++;
        // 记录最小值
        res = min(res, costs[i] + recursive(days, daysSize, costs, index));
    }
    dp[curIndex] = res;
    return res;
}

// 记忆化搜索，时间复杂度O（3n）=O（n）
int mincostTickets(int *days, int daysSize, int *costs, int costsSize) {
    dp = (int *) malloc(sizeof(int) * daysSize);
    for (int i = 0; i < daysSize; ++i) dp[i] = 0x7fffffff;
    return recursive(days, daysSize, costs, 0);
}

int min(int a, int b) {
    return a > b ? b : a;
}

// 自下而上
int mincostTickets(int *days, int daysSize, int *costs, int costsSize) {
    // 每种方案对应的通行天数
    int durations[3] = {1, 7, 30};
    int dp[daysSize + 1];
    for (int i = 0; i < daysSize; ++i) dp[i] = 0x7fffffff;
    dp[daysSize] = 0;
    for (int curIndex = daysSize - 1; curIndex >= 0; curIndex--) {
        // 一共三种方案
        for (int i = 0; i < 3; ++i) {
            // day[index]为下一个需要买票的日子
            int index = curIndex;
            // 可以连续通行的最后一天的后一天
            int nextDay = days[index] + durations[i];
            while (index < daysSize && days[index] < nextDay)
                index++;
            // 记录最小值
            dp[curIndex] = min(dp[curIndex], dp[index] + costs[i]);
        }
    }
    return dp[0];
}

91. 解码方法

int len;

// 返回从curIndex位置往后的字符串有多少种解码方式
int recursive(char *s, int curIndex) {
    // 返回1表示到末尾结束了，之前的解码算是一种方案
    if (curIndex == len) return 1;
    int res;
    // 当前位置是0，无法解码
    if (s[curIndex] == '0') {
        res = 0;
    } else {
        // i位置可以对应一个字符
        res = recursive(s, curIndex + 1);
        int val = (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0');
        if (curIndex + 1 < len && val <= 26)
            // i和i+1位置合在一起也能构成一个字母
            res += recursive(s, curIndex + 2);
    }
    return res;
}

// 暴力法超时，O（2^n）
int numDecodings(char *s) {
    len = strlen(s);
    return recursive(s, 0);
}

int len;
int *dp;

// 返回从curIndex位置往后的字符串有多少种解码方式
int recursive(char *s, int curIndex) {
    // 返回1表示到末尾结束了，之前的解码算是一种方案
    if (curIndex == len) return 1;
    if (dp[curIndex] != -1) return dp[curIndex];
    int res;
    // 当前位置是0，无法解码
    if (s[curIndex] == '0') {
        res = 0;
    } else {
        // curIndex位置可以对应一个字符
        res = recursive(s, curIndex + 1);
        if (curIndex + 1 < len && (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0') <= 26)
            // curIndex和curIndex+1位置合在一起也能构成一个字母
            res += recursive(s, curIndex + 2);
    }
    dp[curIndex] = res;
    return res;
}

// 记忆化搜索，O（n）
int numDecodings(char *s) {
    len = strlen(s);
    dp = (int *) malloc(sizeof(int) * len);
    memset(dp, -1, sizeof(int) * len);
    return recursive(s, 0);
}

int numDecodings(char *s) {
    int len = strlen(s);;
    int *dp = (int *) malloc(sizeof(int) * (len + 1));
    dp[len] = 1;
    for (int curIndex = len - 1; curIndex >= 0; curIndex--) {
        if (s[curIndex] == '0') {
            // 当前位置是0，无法解码
            dp[curIndex] = 0;
        } else {
            // curIndex位置可以对应一个字符
            dp[curIndex] = dp[curIndex + 1];
            if (curIndex + 1 < len && (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0') <= 26)
                // curIndex和curIndex+1位置合在一起也能构成一个字母
                dp[curIndex] += dp[curIndex + 2];
        }
    }

    return dp[0];
}

// 状态压缩
// 类似有条件的斐波那契数列
int numDecodings(char *s) {
    int len = strlen(s);;
    int left, mid = 1, right;
    for (int curIndex = len - 1; curIndex >= 0; curIndex--) {
        if (s[curIndex] == '0') {
            // 当前位置是0，无法解码
            left = 0;
        } else {
            // curIndex位置可以对应一个字符
            left = mid;
            if (curIndex + 1 < len && (s[curIndex] - '0') * 10 + (s[curIndex + 1] - '0') <= 26)
                // curIndex和curIndex+1位置合在一起也能构成一个字母
                left += right;
        }
        right = mid;
        mid = left;
    }

    return left;
}

639. 解码方法 II

待归类

70. 爬楼梯

int climbStairs(int n) {
    int dp[46];
    // 一次爬一层，只有一种方法
    dp[1] = 1;
    // 两次爬一层或者一次爬两层，一共两种方法
    dp[2] = 2;
    int i = 3;
    while (i <= n) {
        // i层可由i-2层爬两个台阶到达，或者由i-1层爬一个台阶到达
        // 爬到i层的方法总数为这两种爬法的方法总数和
        dp[i] = dp[i - 2] + dp[i - 1];
        i++;
    }
    return dp[n];
}

// 空间复杂度O（1）
int climbStairs(int n) {
    if (n < 3) return n;
    int left = 1;
    int mid = 2;
    int right;
    int count = n - 2;
    while (count-- > 0) {
        right = left + mid;
        left = mid;
        mid = right;
    }
    return right;
}

62. 不同路径

int uniquePaths(int m, int n) {
    // 记录到格子（i，j）的路径总数
    int dp[m][n];

    // 初始条件
    // 从（0，0）到第一列的任何一个格子的路径只有一条，就是从上往下
    for (int i = 0; i < m; ++i) dp[i][0] = 1;
    // 从（0，0）到第一行的任何一个格子的路径只有一条，就是从左往右
    for (int i = 0; i < n; ++i) dp[0][i] = 1;

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            // 状态转移方程
            // （i，j）只能由左边的格子或者上面的格子走过来，dp[i][j]就是这两种途径的路径和
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

// todo 空间优化

// 排列组合

第 N 个泰波那契数

int tribonacci(int n){
	if (n < 2) return n;
    if (n == 2) return 1;
    // 初始条件
    int left = 0;
    int midLeft = 1;
    int midRight = 1;
    int right;

    int count = n - 2;
    while (count-- > 0) {
        right = left + midLeft + midRight;
        left = midLeft;
        midLeft = midRight;
        midRight = right;
    }

    return right;
}

// todo 矩阵快速幂

目标和

int res;

// 暴力递归
void dfs(int *nums, int numsSize, int target, int index, int tempSum) {
    if (index == numsSize - 1) {
        if (tempSum + nums[index] == target) res++;
        if (tempSum - nums[index] == target) res++;
        return;
    }
    dfs(nums, numsSize, target, index + 1, tempSum + nums[index]);
    dfs(nums, numsSize, target, index + 1, tempSum - nums[index]);
}

int findTargetSumWays(int *nums, int numsSize, int target) {
    res = 0;
    dfs(nums, numsSize, target, 0, 0);
    return res;
}

// todo