动态规划

左手的ㄟ右手 2021-11-19 14:14 520阅读 0赞

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/75193592\#commentsedit][https_blog.csdn.net_u013309870_article_details_75193592_commentsedit]

核心：记住已经解决过的子问题。

A * "1+1+1+1+1+1+1+1 =？" *
    
    A : "上面等式的值是多少"
    B : *计算* "8!"
    
    A *在上面等式的左边写上 "1+" *
    A : "此时等式的值为多少"
    B : *quickly* "9!"
    A : "你怎么这么快就知道答案了"
    A : "只要在8的基础上加1就行了"
    A : "所以你不用重新计算因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

动态规划有两种方式（自顶向下和自底向上）以斐波那契为例。

自顶向下：

//自顶向下
    public static int Fibonacci(int n)
    {
            if(n<=0)
                return n;
            int []Memo=new int[n+1];        
            for(int i=0;i<=n;i++)
                Memo[i]=-1;
            return fib(n, Memo);
    }
    public static int fib(int n,int []Memo)
    {
    
            if(Memo[n]!=-1)
                return Memo[n];
        //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。               
            if(n<=2)
                Memo[n]=1;
    
            else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);  
    
            return Memo[n];
    }

自底向上：

public static int feibo(int n){
            if(n<=0){
                return n;
            }
            int[] temp=new int[n+1];
            temp[0]=0;
            temp[1]=1;
            for(int i=2;i<=n;i++) {
                temp[i] = temp[i - 1] + temp[i - 2];
            }
            return temp[n];
        }

例题：![è¿éåå¾çæè¿°][SouthEast]

[https_blog.csdn.net_u013309870_article_details_75193592_commentsedit]: https://blog.csdn.net/u013309870/article/details/75193592#commentsedit
[SouthEast]: /images/20211119/1bbfcf23993149368e7d13228ab2d568.png

发表评论取消回复

表情：

评论列表（有 0 条评论，520人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划

一：概念：和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。基本步骤： ①：刻画一个最优

我就是我/ 2022年12月01日 11:51/ 0 赞/ 42 阅读

相关动态规划

-------------------- 动态规划的设计思想动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 266 阅读

相关动态规划

作者：Hawstein 出处： [http://hawstein.com/posts/dp-novice-to-advanced.html][http_hawstein.c

淡淡的烟草味﹌/ 2022年09月24日 12:17/ 0 赞/ 219 阅读

相关动态规划

1. 首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段 2. 动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”

刺骨的言语ヽ痛彻心扉/ 2022年07月29日 11:46/ 0 赞/ 113 阅读

相关动态规划

首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 333 阅读

相关动态规划

> 给定两个字符串A和B，返回两个字符串的最长公共子序列的长度。例如，A=”1A2C3D4B56”，B=”B1D23CA45B6A”，”123456”或者”12C4B6”都是最

以你之姓@/ 2022年06月07日 00:41/ 0 赞/ 332 阅读

相关动态规划

基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：与

ゞ浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 459 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 342 阅读

相关动态规划

1.题目：最长递增子序列（Longest Increasing Subsequence）问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 297 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 521 阅读