Dynamic programming algorithm

1. Frog jump step problem: f(0)=1, F (1)=1, f(2)=2;

// Frog jump step problem
/ * * *@param {number} n
 * @return {number}* /
// Using recursion will exceed the time limit
var numWays = function(n) {
   const Max=1e9+7;
   if(n<=1) return 1; 
   let dp=[1.1.2];
   for(let i=2; i<=n; i++){ dp[i]=(dp[i-1]+dp[i-2])%Max;
   }
   return dp[n];
};
Copy the code

2. Fibonacci sequence problem: F (0)=0, F (1)=1, f(2)=1.

// Fibonacci sequence
// Write a function, input n, find the NTH term of the Fibonacci sequence.
//F(0) = 0, F(1) = 1
/ * * *@param {number} n
 * @return {number}* /
var fib = function(n) {
    const MOD = 1000000007
    if (n<2) return n
    let pre = 0, cur = 0, res = 1
    for (let i=2; i<=n; i++) {
        pre = cur
        cur = res
        res = (pre + cur) % MOD
    }
    return res
};
Copy the code

3. The problem of robbery

/ * * *@param {number[]} nums
 * @return {number}* /
var rob = function(nums) {
    if (nums.length === 0) return 0
    const dp = new Array(nums.length);
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])
    for (let i=2; i<nums.length; i++) {
        dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1])}return dp[nums.length-1]};Copy the code

4. Maximum suborder sum

var maxSubArray = function(nums) {
    const dp = new Array(nums.length)
    dp[0] = nums[0]
    let result = dp[0]
    for (let i=1; i<nums.length; i++) {
        dp[i] = Math.max(dp[i-1]+nums[i], nums[i])
        if (result < dp[i]){
            result = dp[i]
        }
    }
    return result
}
Copy the code

4. Change change

/ * * *@param {number[]} coins
 * @param {number} amount
 * @return {number}* /
var coinChange = function(coins, amount) {
    const dp = new Array(amount +1)
    for (let i=1; i<amount+1; i++) {
        dp[i] = -1
    }
    dp[0] = 0
    for (let i=1; i<= amount; i++) {
        for (let j=0; j<coins.length; j++){
            if (i-coins[j] >= 0&& dp[i-coins[j]] ! = = -1) {
                if (dp[i] === -1 || dp[i] > dp[i-coins[j]] + 1) {
                    dp[i] = dp[i-coins[j]] + 1}}}}return dp[amount]
};
Copy the code

5. Sum of the smallest paths in a triangle

/ * * *@param {number[][]} triangle
 * @return {number}* /
var minimumTotal = function(triangle) {
    const dp = new Array(a)for (let i=0; i<triangle.length; i++) {
        dp[i]=new Array(a)for (let j=0; j<triangle[i].length; j++) {
            dp[i][j] = 0}}for (let i=0; i<triangle.length; i++) {
        dp[dp.length-1][i] = triangle[dp.length-1][i]
    }

    for (let i=dp.length-2; i>=0; i--) {
        for (let j=0; j<dp[i].length; j++) {
            dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]
        }
    }
    return dp[0] [0]};Copy the code

6. Longest increasing subsequence

/ * * *@param {number[]} nums
 * @return {number}* /
var lengthOfLIS = function(nums) {
    if(nums.length === 0) return 0
    const dp = new Array()
    dp[0] = 1
    let result = 1
    for (let i=1; i<nums.length; i++) {
        dp[i] = 1
        for (let j=0; j<i; j++) {
            if (nums[j] < nums[i] && dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1}}if (result < dp[i]) {
            result = dp[i]
        }
    }
    return result
};
Copy the code