动态规划-爬楼梯

题目

https://leetcode-cn.com/problems/climbing-stairs

动态规划

解题

动态规划

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。

第 i 阶可以由以下两种方法得到：

在第 (i-1)阶后向上爬一阶。

在第 (i-2) 阶后向上爬 2 阶。

所以到达第 i阶的方法总数就是到第 (i-1)阶和第 (i-2)阶的方法数之和。

dp[i] = dp[i-1]+dp[i-2];

class Solution {
    public int climbStairs(int n) {
        // 

        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;

        for(int i=2; i<n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1];
    }
}

记忆化递归

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

class Solution {
    public int numWays(int n) {
        if (n == 0) {
            return 1;
        }
        if (n <3) {
            return n;
        }

        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        int mod = (int)1e9+7; 
        for(int i=2; i<n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % mod;
        }
        return dp[n-1];
     }
}

本质上寻找前后项的关系，从上到下递归分解！！从下到上状态方程

2020-07-06

LC63_uniquePathsWithObstacles

动态规划-爬楼梯

题目

解题

动态规划

记忆化递归

Links

Categorias

Nube de etiquetas

Recientes

Archivos

Etiquetas

Recientes

Archivos

Etiquetas

Your browser is out-of-date!