一种是
f(n) = f(n-1) + f(n-2)
变态青蛙跳
考虑第一步走多远 1 2 ... n
f(n) = f(n-1) + f(n-2) + ... + f(n-(n-1)) + f(n-n)
f(n) = f(n-1) + f(n-2) + ... + f(1) + f(0)
f(n-1) = f(n-2) + ... + f(1) + f(0)
所以 f(n) = 2f(n-1) = 2^(n-1)f(1) = 2^(n-1)
然而f(n)是等比数列
用求和公式计算？
这里的坑在于 f(1)=f(0)=1
所以求和的时候需要加上1
image.png
image.png
一种是f(n) = f(n-1) + f(n-2) 变态青蛙跳考虑第一步走多远 1 2 ... nf(n) = f...
A - Frog 1思路：dp[i]: 青蛙跳到i位置最小cost，则动规公式：dp[i] = min{dp[i-...
经典DP
经典递归，dp[i] = dp[i-1]+dp[i-2]，从0 算到n-1 ,返回dp[n-1] dp[0] = ...
问题： 方法：经典的动态规划问题，dp[i][j] = dp[i-1][j] + dp[i][j-1]，然后dp遍...
案例一、简单的一维 DP 剑指 Offer 10- II. 青蛙跳台阶问题[https://leetcode-cn...
1. 最长子序列问题 最长上升不连续子序列 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入:...
青牛卧水眠，牧童骑背欢。 笛声吹柳绿，蛙跳荷叶前。
非常经典的题目了： DP经典题目！ 比较global maximum和local maximum的问题； 首先你要...
经典的dp题：滑雪-dp记忆化深搜 DP 记忆化深搜(1) 如果只有1个点，结果就是1(2) 如果有两个点，从1-...
本文标题：经典DP 青蛙跳
本文链接：https://www.haomeiwen.com/subject/cpbgiqtx.html
网友评论