  
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

algorithm, problems

Algorithm DP

本文由作者按照 CC BY 4.0 进行授权

动态规划简单题

待归类

热门标签