对于奇数，其中必有1这个拆分所以 f(2n+1)=f(2n)

对于偶数，分为两种情况，

111111.拆分中含有1，则与奇数情况相同 f(2n+2)= f(2n+1)=f(2n)

22222.拆分中不含1，所有数除以2， f(2n)=f(n)

所以 f(2n)=f(2n-2)+f(n)

边界条件为f(1)=1

#include<stdio.h>
#include<stdlib.h>
#define MIX 1000000000
int main(){
    int n;
    int dp[1000001];
    scanf("%d",&n);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(i%2==0)
            dp[i]=(dp[i-2]+dp[i/2])%MIX;
        else
            dp[i]=dp[i-1];
    }
    printf("%d\n",dp[n]);
}

动态规划-整数拆分
对于奇数，其中必有1这个拆分所以 f(2n+1)=f(2n) 对于偶数，分为两种情况， 111111.拆分中含有1...
算法练习：整数拆分（动态规划）
一.前言最近一直在了解动态规划，这是LeetCode上面的一道动规的题。 343. 整数拆分[https://l...
动态六：整数拆分
题目地址： https://leetcode-cn.com/problems/integer-break/[ht...
什么是动态规划
目录动态规划解决了什么什么是动态规划典型的动态规划 1. 动态规划解决了什么的思想就是将大问题拆分成小问题...
动态规划（一）
一、动态规划总结 1.1 题目一维斐波那契数列 70.爬楼梯 413.等差数列划分吃烧饼 343.整数拆分 ...
leetcode 343. 整数拆分：动态规划(c++)
leetcode 343. 整数拆分分析状态表示：· dp[i] 表示整数 i 拆分乘积的最大值。转移方程：· ...
动态规划
概念动态规划(Dynamic Programming)，是一种分阶段求解的方法。动态规划算法是通过拆分问题，定义...
JS动态规划算法--01背包问题
动态规划动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。...
最优化模型
数据挖掘之优化模型 1.1数学规划模型线性规划、整数线性规划、非线性规划、多目标规划、动态规划。 1.2微分方程...
leetcode 5最长回文字符串
这个题感觉不太好想，对于动态规划不太熟练，导致遇到这种可以拆分成子问题的题目想不到解法，并且感觉能用动态规划来解的...