动态规划中包含3个重要的概念：

1.最优子结构 2.边界 3.状态转移公式

以跳台阶为例，最优子结构为f(10)=f(9) + f(8)，边界是f(1)=1, f(2)=2，状态转移公式f(n)=f(n-1) + f(n-2)

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解法1

首先对这道题，我们可以通过找规律来解
一只青蛙可以跳上1级台阶，也可以跳上2两级台阶
当n = 1时，有1种跳法
当n = 2时，有2种跳法
当n = 3时，有3种跳法
当n = 4时，有5种跳法
当n = 5时，有8种跳法
...
等等，1，2，3，5，8...，多么熟悉的数列，斐波那契？
仔细想想当有n(n >= 2)级台阶时，求F(n)
青蛙第一步可以选择跳上1级台阶，则还剩n - 1级台阶需要跳，即F(n - 1)
青蛙第一步也可以选择跳上2级台阶，则还剩n - 2级台阶需要跳，即F(n - 2)
则总的跳法F(n) = F(n - 1) + F(n - 2)，毫无疑问这就是斐波那契数列的定义了。

最长回文子串

方法三：动态规划
为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑“ababa” 这个示例。如果我们已经知道“bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

C++的动态规划写法：

class Solution {

public:

    string longestPalindrome(string str) {

        const int n = str.size();

        if(n < ) return str;

        int s = , e = ;

        int dp[n] = {, };

        for(int j = ; j < n; ++j){

            for(int i = ; i < j; ++i){

                if(!(dp[i] = dp[i + ] || str[i] != str[j]) && (e - s) <= (j - i))

                    s = i, e = j;

            }

        }

        return str.substr(s, e - s + );

    }

};

令dp[j][i]从字符串j到i是否为回文串

动态回归方程 dp[j][i]是看j+1和i-1是否为回文串.

class Solution(object):

    def longestPalindrome(self, s):

         n = len(s)

        dp = [[0] * n for _ in range(n)]

        max_len = float("-inf")

        res = ""

        for i in range(n):

            # dp[i][i] = 1

            for j in range(i, -1, -1):

                if s[i] == s[j] and (i - j < 2 or dp[i - 1][j + 1]):

                    dp[i][j] = 1

                if dp[i][j] and i - j + 1 > max_len:

                    max_len = i - j + 1

                    res = s[j:i + 1]

        # print(dp)

        return res

class Solution {

    public String longestPalindrome(String s) {

        int n = s.length();

        String res = "";

        boolean[][] dp = new boolean[n][n];

        for(int i = 0 ;i < n; i++){

            for(int j = i; j >= 0 ;j --){

                if(s.charAt(i) == s.charAt(j) && ( i - j < 2 || dp[i-1][j+1]))

                    dp[i][j] = true;

                if (dp[i][j] && (i - j + 1 > res.length())){

                    res = s.substring(j,i+1);

                }

            }

        }

        return res;

    }

}

巴特西

Leetcode代码复盘_动态规划

动态规划中包含3个重要的概念：

题目描述

解法1

最长回文子串

最新文章

热门文章